Tuesday, June 24, 2008


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 (hi), and the length of his arms (li). 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, hi, and li, 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(n2). Can you do better?

Friday, June 20, 2008

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).

Thursday, June 19, 2008

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.

Saturday, June 7, 2008

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.

Tuesday, June 3, 2008

Best Of, Take Two

First of all, appologies for the last post. I managed to explain the purpose of the game very badly. It generated a long list of names of very common suspects, which of course contained zero information.

Now let's try to fix it. Please nominate your favorite theory researcher, together with a 3-line description of the reasons for your nomination. I imagine a comma-separated list of results would work very well, as would more complex explanations.

With this ammendment, maybe we can answer the original questions of (1) understanding how we appreciate researchers these days -- actually state a short explanation for why we value these people; (2) having a somewhat meaningful narrative for the junior people who might ask such a question -- a list of names without any justification is not so inspiring, since they haven't been exposed to our mob's peculiar mentality.

Also, here are the rules to keep this interesting and decent:

  • only post anonymously;

  • feel free to ask for clarifications on somebody else's nomination. What the heck, post rebuttals if you like;

  • understand that this is just a summer game for a bit of fun and a bit of understanding the community we live in (I think it would be enlightening to see what our peers value);

  • focus on the goal is to understand what we value, and ignore the impact that your nomination (or rebuttal?) might have on a specific person. Of course all these people are too senior to care whether some anonymous commenters on my blog like them or not :) You don't need to make them happy, and there no way you're realistically going to insult one of them...

  • don't complain that there's no way to compare so many uncomparable people. I am hoping we're all old enough to understand the impossibility of such a pure comparison. Be subjective! That's what we want to understand -- out community's subjective thinking.

Best of?

Today was the third time in a couple of months when I was asked to make a "most super of the superstars" list for TCS. I never had anything close to a good answer, so let's hear it from the readers of this blog :)

Please nominate people for the following 2 categories:

  1. "best" 5 TCS researchers ever;
  2. "best" 5 TCS researchers based on work from the past 15 years only.
If this is not obvious, the purpose of the best-of list is not to give these people some praise. I'm sure they couldn't care less about how much some anonymous commenters on my blog like them :)

It's also not to say that brilliant work in TCS is concentrated in the papers of these 5 guys. Some of the best results ever came from people with just 1 or 2 nice results in their entire career, and presumably these people will not be on the best-of list.

The purpose of these nominations is to see what we tend to appreciate in TCS these days, when it comes to appreciating researchers instead of results. From the questions I'm getting, it seems junior people need a few role models while struggling to get started, and it would be nice to let them pick an idol or two :)

This is one of the few posts where I would appreciate anonymous responses, but please think seriously about your nominations (top 5 makes for a nontrivial threshold).