Thesis Defense

Yesterday, I defended my non-existent thesis, apparently with success. (The thesis itself will be done on August 29, at or around 2:58pm. There are plans to make it readable.)

Here are the slides from the defense in PPTX (also saved as PPT with minor screw-ups). Sorry, no reasonable PDF. Due to lack of time in making the slides, a lot of the presentation was verbal commentary, but hopefully the slides also have some value.

In other news, I am once again fed up with Powerpoint, and I will be switching back to LaTeX/Beamer. Last time I quit Beamer because xfig sucked, but in the mean time I discovered TikZ and it is impressive.

By the way, when discussing the history of cell-probe lower bounds, it occurred to me that the two major foundational papers that really started the whole field were:

• [Ajtai 88], published in Combinatorica, but proving a false result.
• [Fredman, Saks 89], published in STOC, containing tons of claims without proofs, and not followed by any journal version.

Idiots. It's not as anybody will remember them 20 years later for starting an entire research field. Research is about proving immortal theorems that represent absolute truth. This requires triple-checking of all proofs, and inclusion of absolutely all details (even in SODA submissions). The proofs of such absolute truth must be deposited in journals for perpetual archiving*, thus preserving the name of the author forever.

[[ *Though paper is an almost perfect solution to preserving your ideas into cold immortality, some care must be exercised. To prevent ware and tare, it is recommended that your piece of absolute truth does not motivate any reckless readers to actually open the journal at the pages of your paper. ]]

Incidentally, these two papers are also the "second paper" in the field (after Andy Yao defined the model a decade earlier). This reminded me of Luca's very sensible "second paper" observation.

Algorithms for Farey Sequences

I recently uploaded the final version of my paper with Jakub Pawlewicz, due to appear in Algorithmica. The paper has a sparkling story (from my own perspective, at least) that should be told.

Starting research. In my glorious freshman year at MIT, when I was working on P vs NP and convincing random professors to pay me, I was trying to understand what research meant. This was not an easy task, since the closest thing I had to a mentor was Alex, who had just started research the previous summer. (Erik didn't quite qualify, since my second meeting with him was 3 or 4 months after he had started paying me.)

In any case, the lesson that I managed to absorb from the environment was that you're supposed to ignore all the cool stuff that's in books, and come up with new algorithms that were not known before Earth was graced with your existence. Then, you write papers describing these new algorithms, and you join the cool club of people who are in the business.

Judging that I might not have a paper on P vs NP soon, I decided to start looking for other problems, and I remembered a book on algorithms that I had read in middle school. This was the kind of book that Romanian associate professors write (because you need to have a number of books before becoming full professor): it contained all sorts of unrelated random topics that the author had come across since writing his previous book. Next to planar closest pair in O(n lg n) was a discussion of Farey sequences and an optimal algorithm for generating them. (See my older post for a definition of Farey sequences and a cool application.)

As soon as I remembered this algorithm, I saw potential for a "result": if we ask for just the kth element of the sequence, can we obtain a sublinear algorithm that doesn't generate the whole sequence? Here "sublinear" means better than O(n²), because the Farey sequence of order n has O(n²) elements. Of course, there is no real motivation to this problem, but this didn't bother me at the time.

A result. Soon enough, I had an algorithm running in O(n lg n) time, and summer was coming up. I was a member of the Scientific Committee of the Balkan Olympiad in Informatics happening that summer, so I assigned the problem in the competition. (Don't worry, I'm not a big fan of assigning "unrealistic" problems, so my time bounds allowed for an easier and less efficient algorithm that I had discovered at first. Even so, it turned out to be the perfect "hard problem," that required some unusual ideas and was solved only by a couple of people.)

Returning to "research mode," I used Google to check if my result was known (seemed not), and discovered the Algorithmic Number Theory Symposium (ANTS). I then wrote a paper with my ex and sent it to the conference. Looking at it in retrospect, it looks like a very childish paper. Nonetheless, Math conferences are not competitive, and it got accepted. The referee report contained the best polite equivalent of "the authors don't know what the heck they're talking about" that I have yet seen. It read: "The authors unintentionally hide the fact that the quantities A(.) that they define in the course of the solution are actually the Mertens function."

At the conference, people were entertained by the paper. They asked if we could get an O(poly(lg n)) algorithm on a quantum computer (I maintain my original response: What??), and asked whether we could count primitive lattice points inside polygons efficiently. A primitive lattice point is a point (x,y) where x and y are coprime; the Farey problem can be reduced to counting primitive lattice points in a special class of triangles.

I kept thinking at odd times about getting a faster algorithm, and about counting primitive lattice points in larger classes of polygons. I had a complicated algorithm running in O~(n^3/4) time, and some results for primitive lattice points. However, by then I was engaged in doing research on more high profile problems, and I could never get myself to write another paper on this topic.

Shock and awe. As it turns out, not publishing a follow-up was a brilliant decision. Last year, Krzysztof flew to California for my birthday party. Before the discussion got elevated by consumption of alcoholic beverages, he managed to tell me that Jakub Pawlewicz, a student at his alma mater in Poland, had written a follow-up paper about algorithms for Farey sequences. As it turned out, Jakub had a very nice algorithm achieving O(n^3/4) time.

At first, I was amused and surprised by the fact that someone had actually picked up the problem! Then, I found out that the paper was accepted to ESA'07, and I was even more surprised (I had never considered mainstream CS conferences for such a problem). But only when I found out that it got the Best Student Paper Award at ESA, was I totally blown away!

Now, had I published my follow-up paper, then almost certainly history would have been different. I would have never found out that the best student paper at ESA can be won for a follow-up paper to something I did in freshman year! As you can imagine, this made for some entertaining pub discussions, like:

Admired top-notch researchers get research awards. Also, there are some godly figures, so established, so influential, that research awards are being handed out for works in the fields that they created. But who else can claim that research awards are being given for work in a field that they introduced in freshman year? :)

The aftermath. Despite the entertainment value, getting scooped was not entirely a nice feeling, since I am, like any researcher, a bit attached to my results. My consolation was that Jakub is also a former medal winner at Informatics Olympiads (IOI and CEOI), so at least I had been scooped by a very worthy person.

Fortunately, I lucked out for the second time. I asked Jakub for the paper, and his solution was so clear and elegant, that I found it easy to plug my old ideas into it. Within the hour, I saw how to improve his algorithm to O(n^2/3) and was writing him an email about it. Yes, I imagine he hates me for this episode :)...

In the end, we merged the two results into the paper I mentioned in the beginning, which appears in the Algorithmica special issue for ESA'07. This was the ideal outcome for me: I got my ideas published with minimal effort, and with a bonus story.

Open Access?

I recently received an invitation to join the editorial board of a new journal called Algorithms, which claims to be an open access journal. Circumstantial evidence suggests the invitation was distributed to more than a handful of people. The list of people who have already accepted contains some established members of the community, as well as many names I have never heard before.

The main idea of this particular publisher is to have a publication model in which authors pay to get published (in the neighborhood of 1000 dollars!), and readers can access the papers for free on the Internet. Though you may choose to call this "open access," I profoundly dislike the name. As soon as you attach a big cost at either of the two ends of the business (publishing or reading), it stops being "open." It seems to me that we have another case of a creative publisher trying to scheme us into paying them large amounts of money for no value added.

You will not find my name on this editorial board.


While on the topic of open access, I must say that all my support is behind Theory of Computing. This wonderful initiative gives us a truly open access journal (zero cost for everyone), and a journal of superb quality. Based on articles published so far, I view ToC as being in the same constellation with SICOMP.

In the unlikely future universe in which I will not be overcommitted by several notches above the sanity level, I will be able to do things without deadlines. Then, I may write some journal papers without the deadlines/incentives of special issue, and I will try to send them to ToC.

Dwarves

Last week I was at the Romanian training camp for the IOI, after several years of absence. (If you don't know what I'm talking about, I wrote a series of posts about informatics olympiads a while ago.) To my great surprise, I was still able to solve the competition problems :)

Unlike Math, CS doesn't have a culture for tough puzzles, i.e. problems that are not "important" for any reason, but are fun and intellectually challenging. Perhaps the difference is that CS folks are vastly superior to Mathematicians when it comes to bull-shitting (our ability to draw targets around any arrow we shoot makes all our problems "serious research"...)

In any case, here's a rewarding problem from the competition, for your own enjoyment. It captures my intuitive notion of a "CS puzzle" very well, but beware: it is not a trivial puzzle. (It may have taken me one hour of thinking, of course in my current rusty state.)

Dwarves. n dwarves fell in a hole that is H meters deep. Each dwarf is characterized by the distance from his feet to his shoulders (h_i), and the length of his arms (l_i). Dwarves can pile up as a tower, with each dwarf sitting on the shoulders of another. The dwarf at the top of the tower can climb out of the hole if his hands, stretched up, can reach to the top.

Given n, H, h_i, and l_i, find the maximum number of dwarves that can escape from the hole (through forming towers as above; of course, once a dwarf escapes he cannot take part in another tower).

Desired running time: O(n²). Can you do better?

FOCS and Euro

I finished watching a spectacular game at Euro 2008 between Turkey and Croatia. It went into overtime with both teams obviously stressed by the importance of the match. Croatia scored 3 minutes before the end of overtime, prompting a huge display of joy among supporters. But Turkey never stopped believing, and in minute 122 (two minutes past the official end of overtime and seconds before the final whistle) scored to tie the game. Then the joy of Turkish supporters made the Croatian moment seem like nothing. Turkey eventually won on penalty kicks.

I then returned to life, and checked to see why my Blackberry had been buzzing so much. I saw 4 accept notifications for FOCS 2008, and realized that supporters may cheer, but it's nothing like the feeling of joy for the players.

As always, my 4 submissions can be found on my papers page (top 4).

LSD Randomized Lower Bounds

Apparently a few people took issue with my (Data) Structures paper because it claimed a randomized lower bound for LSD without a proof, and this propagated to the FOCS PC. I recently received an email from the PC asking for a sketch of the proof, pronto.

As I explained before to anon commenters on this blog, I don't know what the big fuss is about. The paper is certainly not trying to claim credit for this proof (it is not even mentioned in the introduction). It's just trying to say "yeah, we know how to do it, and it's not interesting; don't waste your time on it." The results of the paper are interesting independently of any LSD proofs. If you don't like my claim, you only get deterministic lower bounds (see here for deterministic LSD lower bounds, which were known since STOC 95). No big loss.

But since I had already claimed that the randomized LSD lower bounds are straightforward (once you understand the literature), I had the moral obligation to support my claim. So here is my PDF response, in which I give a (sketch of a) proof for the randomized bounds. Don't be too harsh on this; due to the whole context I only had a few hours to write the thing, so some calculations of constants are left out. The writing is also bad, but hopefully if you're actually interested in the topic you already know enough to follow.

I think we need to grow up as a discipline, and understand that the ideas of a paper are not measured by the formula depth. If it's painfully complicated (which this proof is), it doesn't mean it's actually interesting or cool or worthy.

Being Rich (II): Motivating LSD

We now continue our introduction to asymmetric communication complexity and its applications. In the first episode, we showed a deterministic lower bound for Lopsided Set Disjointness: Alice and Bob each have a set (of very different sizes), and they want to communicate to determine whether the sets are disjoint.

But are we using LSD just for entertainment, or is it a fundamental to our understading of the world? (Ahem.) In this post I want to convince you that LSD is a truly fundamental problem, something like the root of all evil in data structures. You will hopefully be motivated to continue watching this "Being Rich" series very carefully.

The central importance of LSD was understood in a recent paper entitled (Data) Structures that I submitted to FOCS. Quite possibly, it is the best paper I've written so far.

In this paper, I show that a lot of data-structure lower bounds can be shown directly by reduction from set disjointness (and by a lot, I mean almost all known ones, and several new ones). This leads to greatly simplified proofs of many known results, as well as several new and interesting lower bounds.

Since a picture is worth 1000 words, here it is:

For the problems in red, we get better results that what was previously known. For the rest, our reductions simplify existing proofs. The solid arrows are the new reductions, where all the magic happens. The dotted arrows are known or folklore reductions.

If you don't know what these problems are, or if you want to know about the reductions themselves, just hold until the sequel posts. This post is merely ment as an appetizer :)

Note that our tree contains problems from very different "classes" of data structures, for which previous lower bounds used very different techniques with with no suspected relationship:

• dynamic problems, where we study the trade-offs between update and query times.
  
  
• "easy" static problems, which can be solved in some poly(lg n) time with space O(n polylog(n)). One usually asks for the best possible query time with space O(n polylog(n)).
  
  
• "hard" static problems, typically suffering for a course of dimensionality. Upper bounds typically involve very large space (often superpolynomial).
  

The way I see it, this paper is a classic example of scientific luck :) Each reduction is technically easy, but the overall result is conceptually hard: you need 2-3 reduction steps, and you need to magically come up with the intermediate problems in the reduction chain (the most unexpected being reachability oracles in butterfly graphs). I was very lucky to be looking at precisely the right problem at the right time, and this beautiful tree suddenly came together.

To finish on a funny note, let me summarize the 3 different feelings that I have had towards this paper:

• Oh cool! Putting structures in "data structures." Now the complexity types have no excuse not to pay attention :)
  
  
• Finally, I can teach some lower bounds! All I need is a very simple bound for LSD, and then it's all clean reductions instead of lower-bound mess. I can even assign some of the simple reductions as homework!
  
  
• :( ... The beautiful theory and understanding that we've been building for 20 years collapses to one single problem. We know so little. We're now just like main-stream complexity, big dreams and few proved lower bounds.