Social Aspects of Blogging

Whenever you write something that contains a number of paragraphs and tries to have some kind of point, and you see a flame-war starting about one word in the writing (which by definition is misinterpreted because it's taken totally out of context), you remember how weird people are on the Internet.

People who in live conversation can't articulate more than a few ambiguous statements while struggling hard not to look at you --- well, all of a sudden these people develop big and aggressive Internet personas, they start having strong opinions etc, of course all expressed under the strict veil of anonymity.

And there are the entirely normal, decent people, who still can't help flaming on the Internet. After all, in person and non-anonymously, there is a higher cost to jumping at someone's throat, and you stop and think --- did I actually pay attention to what he's saying, did I try to find the point behind the statement as opposed to jumping at form? Anonymously, on Web 2.0, the cost is null, so there's not much incentive to stop and think.

No matter what you think of my own opinions (which of course are hardly new or concealed from the general public), you will agree with me that it is sad to see statements that begin with "You are entitled to your opinion," and end with:

You really ought to pay more attention to filtering out your ambition-induced half-baked biased perceptions about the world you are privileged to have around you.

Dear anonymous commenter, sorry to say, but this sounds too much like a 5-year old with tears in his eyes. I can't believe you're wasting so much mental energy getting so worked up over word-choice in a blog. Come on!

The same goes to whoever is writing detailed meta-theories on what Mihai actually thinks and says. Don't you have better things to do? I'm actually sorry to waste your time on this --- especially since it's likely you're totally decent people in live conversation, whom I might actually enjoy talking to.

I, for one, have better things to do than agonize about how to make my posts misinterpretation-proof. If you continue reading, which by the way you don't have to, then you implicitly agree that things will be rough around the edges.

When I originally started blogging, one of the motivations was that I could communicate a message much more effectively. That sort of works for technical issues, but I am now convinced that it mostly fails for "social" issues. The cost of getting annoyed over the Internet is so low, that everything degenerates into useless quarreling, which changes few opinions. In addition, ignoring whatever doesn't quite match your own perception is very easy. In the best case, you remember that "Mihai thinks that," but you never fully internalize the argument as in face-to-face discussion.

So, as I have done for several months now, I will limit social commentary on the blog. Of course, since I never take principles entirely seriously, you can be assured that personal opinions will pop up every once in a while.

Correctness?

I am experiencing the joys of being on a Program Committee (in this case SWAT'08).

• famous person A submits a paper claiming an interesting result. The writing is bad.
• famous person B, tricked by yours truly into refereeing the paper, claims said result is wrong.
• my principle for (in)correctness claims is to contact the author directly.
• A responds (retaliates?) with a link to a 40-page full version.
• B reads the full version (I guess it's personal by now), and sends back a detailed meta-argument for why the proof is wrong.

In the end, there's no hope to referee the full version and find an actual, concete bug (if one exists). So we're stuck with general arguments.

I am told to write a negative comment based on the paper being poorly written, and not mention anything about correctness. But somehow, washing my hands of the paper is not quite my style...

The politically-correct (PC?) alternative is to convince the authors that the result is too hard/long/etc for the conference, and they should submit it to a journal where complete refereeing is feasible


Oddly, this reminds me of freshman year, when I was starting in theory. When I heard of conferences and journals, my natural assumption was that papers would just be published in journals, and the best would be invited to conferences (soon after publication), as a label of quality, and to allow quick dissemination of important ideas. I remember a very confused Alex saying "I really mean, they do it the other way around."

End of Trip

After almost 3 months, I'm back to MIT.

I flew out of Luxemburg this morning, biked to Hague for lunch with a high-school friend, and now I have a few hours before attending a big Romanian party at MIT. Life is good.

Since I mention Luxemburg, I must add that I found it a remarkably beautiful city, even compared to the big European classics. Definetely worth visiting, especially for those of you who occasionally go to Dagstuhl (also note that LUX is significantly closer than FRA!)

At Dagstuhl, I gave two talks (Onlinifying Ian and Hard Data-Structure Problems), had enlightening conversations, but above all, I presented my new Romanian outfit:

(Picture courtesy of Sariel.)

The border-control dog seemed horrified by the smell of my baggage and disappeared as quickly as it could, dragging the attendant with it. I am left guessing whether it felt some faint smell of wolf or sheep blood that we cannot sense.

Talk, Univ. de Vest, Timisoara

This Friday, February 15, I am giving a talk at Timisoara, hosted by Gabriel Istrate. The talk is roughly an overview of the world of dynamic graph algorithms (no background assumed) --- what are the milestone results, the current research, and the big challenges for the future.

When it comes to current research, I will understandably be biased towards my own work, and will talk primarily about:

• how to generalize graph bridges to understand multiple edges going down (this paper with Mikkel Thorup). Big open problem: worst-case bounds.
• how to handle node failures, not just edge failures (this paper with Timothy Chan and Liam Roditty). Big open problem: handling node failures better and for more queries.

Formal details for those who want to attend:

Locatia: Universitatea de Vest. Sala 045C (Institutul e-Austria)
Ora: 10:00 am (vineri, 10 februarie)
Titlu: Algoritmi pentru grafuri dinamice
---
In multe aplicatii naturale, grafurile cu care avem de-a face au o structura dinamica: conexiunile (muchiile) dintr-o retea de calculatoare se pot strica sau repara; o configurare gresita sau un reboot poate scoate din folosinta un router (nod in graf); etc. Aceste cerinte au dus la un studiu intens al algoritmilor pe grafuri dinamice, care dureaza de peste 20 de ani si nu pare sa se apropie de sfarsit.

In aceasta prezentare, nu vom presupune cunostiinte anterioare despre grafuri dinamice, si vom incepe cu o introducere a domeniului. Apoi ne vom concentra pe cateva rezultate recente, si vom discuta multitudinea de probleme care raman inca nerezolvate.

Introducing TCS?

What do you present in a 2-day course with an audience who is:

• really smart
• generally unaware of TCS, but willing to spend time listening to you
  
• half (non-theory) computer scientists and half hard-core theoretical mathematicians?

With a few hours to decide and 2 mornings to prepare, I designed the course detailed below. I hope this contained enough brain-teasers, cool ideas, and real applications to be an effective introduction to TCS. But I am very curious to hear about some "must-teach" topics that I forgot --- leave a comment.

----- Day 1 -----

Nearest Neighbor in the Plane. Voronoi diagrams, point location with O(n) space and O(lg n) time via persistent data structures.

• historical references: the autoritative paper is [Driscoll, Sarnak, Sleator, Tarjan: Making Data Structures Persistent. JCSS 1989; STOC 1986]. The initial papers were [Sarnak, Tarjan: Planar Point Location Using Persistent Search Trees. CACM 1986]; [Cole: Searching and Storing Similar Lists. JALG 1986]
• today these results are described in many places. See for example these lecture notes from David Karger's Advanced Algorithms.
  

Going below logarithmic time. Talk briefly about the field of TCS exploring sublogarithmic running times, which is also one of the few areas where we have good lower bounds. I only taught van Emde Boas as an example, but mentioned a lot of things:

• my paper with Timothy Chan on sublogarithmic point location. Open problem: lower bound.
• my paper with Mikkel Thorup giving optimal lower bounds for predecessor search. (In particular, van Emde Boas is optimal for near-linear space.)
• my favorite algorithm for sorting in o(nlg n) time is signature sort, which sorts in O(n) time when the word is w = Ω(lg^2+ε n). See for example these lecture notes from our Advanced Data Structures course.
• if my presentation of van Emde Boas managed to confuse you, check out one of the many expositions, such as these lecture notes from our course.
  

Nearest Neighbor in Constant Dimension. Curse of dimensionality: Voronoi diagram grows like n^O(d). Space-filling curves: how to get (1+ε)-approximation in any constant dimension, with linear space and predecessor query time.

• this is mostly from [Chan: Closest-point problems simplified on the RAM. SODA 2002]. Paper here.
• I blogged about this a while ago.

High dimensions. Brief motivation of high dimensions (machine learning "features" and such). Stories and intuition about L_p norms; how God seems to love L₂. Johnson-Lindenstraus, with proof. Brief story about approximate nearest neighbor (LSH and n^{1/ε^2}); lower bounds.

• there are many expositions of JL. For some very complete proofs, see these lecture notes from Michel Goemans' class.
• the latest LSH paper, with a good bibliography, is [Andoni, Indyk: Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, CACM 2008]. You can see it on the new and nifty CACM webpage (click the Contents button, then it's on page 117).
• our lower bounds on JL-based algorithms.

Norm estimation in the streaming model. Why we care: query plans, and optimization in SQL engines. Estimating the L2 norm via Johnson-Lindenstraus. Overview of other norms.

• the original paper, now with a Goedel award: [Alon, Matias, Szegedy: The Space Complexity of Approximating the Frequency Moments. JCSS 1999, STOC 1996]
• I believe the latest paper is [Indyk, Woodruff: Optimal Approximations of the Frequency Moments of Data Streams, STOC2005]
• for a nice description of norm estimation, and a whole lot more about streaming algorithms, see Piotr's class
  

----- Day 2 -----

Define graph sparsity. Examples; handwave about planar separators and algorithmic applications. [What is a good citation for this topic?]

Expander graphs. Handwave about explicit constructions. 2-minute overview of pseudorandomness. Randomness-efficient amplification via random walks on expanders.

• An excellent introduction to pseudorandomness is Salil Vadhan's course. If I got you confused, lecture 8 concerns error reduction by expander walks.

Metrics. Embeddability, any metric embeds into L1 with distortion O(lg n).

• a whole course on metric embeddings, by Michel Goemans.
• CRC bookchapter by Piotr Indyk and Jiri Matousek.
• there is a ton of recent work (particularly lower bounds = nonembeddability) that I cannot hope to link to here.
  

Sparsest-cut problem. Why we care out graph partitioning, and bit about practice. Theory: cut metrics; L1 = cone of cut metrics; use LP to optimize over all metrics and then embed into L1. Handwave about negative-type metrics, SDPs, and O(sqrt(lg n)) approximation.

• the famous paper that first used embeddings for sparsest cut is [Linial, London, Rabinovich: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 1995, FOCS 1994]
• the sqrt(lg n) paper is [Arora, Rao, Vazirani: Expander Flows, Geometric Embeddings, and Graph Partitionings. STOC 2004]. See here.
• a lot of recent (and not so recent) research has been done about this problem. A personal favorite here is [Spielman, Teng: Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, STOC 2004]

Minicourse at Univ Bucharest

Update: The room is 220 (second floor) at the University of Mathematics. See you Thursday.

Original post:

On Jan 31 and Feb 1 (Thursday and Friday), I am giving a minicourse at the University of Bucharest. It extends far beyond my own research (rough topic is "geometry in theoretical CS"). I am hoping that it will provide a taste of what modern algorithmic research is like, as well as present some really cool algorithms.

The course begins at 3pm each day. The room will be announced here in a few days.

In good theory tradition, I hope you will also come to a beer on Thursday evening, after the course. Details to be arranged.

The language will be Romanian. See below for announcement:

Titlu: Perspective geometrice in dezvoltarea algoritmilor

Abstract:
Cum ajuta o constructie Cantor pentru cardinalitatea numerelor rationale la obtinerea unor structuri de date eficiente? De ce estimarea normelor in dimensiuni inalte este necesara la optimizarea cautarilor in baze de date? Cum pot progrese in intelegerea geometriilor ne-euclidiene sa ajute la constructia microprocesoarelor?

Perspectiva geometrica s-a dovedit din ce in ce mai utila in progresele recente in dezvoltarea algoritmilor. In acest curs, vom discuta cateva idei matematice reprezentative, si cativa algoritmi frumosi care se obtin.

Cursul este la nivel introductor si speram ca va contine idei interesante si pentru informaticieni care urasca matematica si pentru matematicieni care urasc informatica.

Travel Update

First of all, yes, I'm alive and rather well. :) Perhaps the biggestproblem is that I've been Net-deprived for about a month.

Thanks to all the people who have sent me worried email about the Kenya situation; all was ok for me, and please accept my appologies for not replying in time.

Here's a short list of what has happened. I promise to ellaborate infuture posts.

• Jinja, Uganda: some of the best rafting in the world, due to thetruly unique features of the White Nile.
• Semuliki Valley, Uganda: avoid the Ebola outbreak, visit the pigmies, see geysers, travel with 20-something people and 3 chicken on the back of a pick-up truck
• Christmas, Ugandan style in Kasese
• Queen Elizabeth National Park, Uganda: get mock-charged by a lion, break personal speed record for running 100m, calm down and go on jeep and boat safaris
• Sipi Falls, Uganda: get disgusted by Ugandan tourism industry, get arrested and exercise negotiation skills
• return to Western Kenya from Christmas break. Unknowingly wonder why buildings have been burned and there's nobody on the streets.
• hear horror stories from town (5-7 dead per night while we were there) and evacuation stories from Kisumu. Experience living withKikuiu refugees, no supplies, and 6 liters of gas between 4 cars.
• bribe a priest to convince bar owners to get out of their basements and sell me all beer they had. I cleaned the village, and got 27 bottles of beer (for 15 people), making for a great New Year's party.
• evacuate to Uganda. Soon thereafter, the farm was attacked due to the Kikuiu refugees there. I'm now facing several weeks of forced vacation -- a very weird feeling.
• find our way across Uganda to Tanzania, in the middle of an economic collapse (no supplies passing from Kenya).
• cross Lake Victoria on ferry. A boat is never ever sold out in Africa; the question is the bribe needed to get on.
• meet an American drug dealer, vacationing in Africa. See him get arrested while he's trying to buy something for own consumption, and hear how he talked his way out in 4 hours.
• climb Mt Kilimanjaro! Be the first on top that morning, only to see your guide start to struggle with headaches and dizziness. Then go into hypothermic shock yourself; spend some time shivering on the bottom ofa cave, as you remark that you have lost all sensation and control in your arms. Fortunately all ended up well.
• for the rest of the forced vacation, I am in Zanzibar, where everything is peaceful and touristy. The Indian Ocean is a fabulous underwater experience.

Well alright, everything is almost peaceful. I collided with a Sea Urchin, and about 2 dozen needles penetrated my foot and broke in there. It made for some pain and a numb leg for a day.

Not to waste the time here, I decided to go back to school, in particular scuba-diving school. The dives are truly wonderful.