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.
  

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

Being Rich (I)

[Updated May 26: writing improved based on a "referee report" by an anonymous commenter. Let me also point out that use of paper and pencil while reading this text is encouraged.]

Let switch gears from politics to science... I am going to run a short series of posts talking about asymmetric communication complexity and how it relates to data structures. In this post, I start by defining the problems and the model, and give a simple (but very interesting) example of a lower bound.

No background is assumed. I believe a high school student should be able to follow this as a gentle introduction to lower bounds. (Yes, yes, I mean a high school student educated in Easter Europe, who knows the European "basic Math." For example, we use (1 + 1/n)ⁿ --> e at some point.)

If there are steps that you want clarified, you are welcome to post a question.


Set disjointness. Today, we start with a simple, abstract problem: set disjointness. Let's say Alice has a set S, Bob has a set T, and they are trying to communicate somehow, to determine whether S and T intersect. To quantify the problem, say |S|=n, |T|=m, and both sets come from a universe [u]={1,...,u}.

For now, we will only be interested in deterministic communication protocols (as opposed to protocols using randomization). In "symmetric" communication complexity, we are primarily interested in the dense case, n=m=Θ(u), and we ask how many bits of communication Alice and Bob must exchange to solve the problem correctly.

The trivial upper bound is u+1: Alice sends a bit vector of size u, specifying her set, and Bob replies with the answer. Alternatively, Bob can send his bit vector, and Alice computes the answer. It can be shown easily (see below) that any protocol must use Ω(u) bits of communication in the worst case, so the trivial protocol is asymptotically optimal.

In the asymmetric case, assume n<<m, and m=Θ(u). Because the input sizes are rather different, it is more interesting to measure the number of bits sent by Alice and Bob separately, instead of measuring the total communication. Denote by a the number of bits sent by Alice throughout the protocol, and b the number of bits sent by Bob.

Clearly, there is a trade-off between a and b. The trivial protocols from above give two points on the trade-off curve. Alice can describe her set using a = lg(u choose n) = O(n lg(u/n)) bits, and Bob replies with b=1 bit. Alternatively, Bob can describe his set using b=u bits, and Alice replies with a=1 bit.

Pause for a second, and try to come up with the best trade-off curve interpolating between these two extreme points.

x
x
x
x
x
This space intentionally left blank.
x
x
x
x
x

Here is how the trade-off looks like:
Values of a = o(n) are ineffective, i.e. Bob cannot save asymptotically over sending u bits. Similarly for values of b=o(n). The interesting portion of the trade-off is the curved one, which is described by: b = u / 2^O(a/n).

Here is how we can achieve this trade-off. First, let k≥a be a parameter. We break the universe [u] into k blocks of roughly equal size, u/k. Now:

• Alice begins by specifying the blocks containing her elements. This takes a=lg(k choose n) = O(n lg(k/n)) bits (if there are fewer than n distinct blocks, pad arbitrarily).
• for every block containing an element of Alice, Bob sends a bit vector of size u/k, specifying which elements are in T. This takes b = nu/k bits.
• Alice replies with one more bit giving the anwer.

We have a=O(n lg(k/n)) and b=nu/k. Now eliminate the parameter: k=n*2^O(a/n) and thus b = u / 2^O(a/n).


Lower bounds. We are now going to prove that this trade-off is the best possible for determinstic protocols. This proof originates from [Miltersen, Nisan, Safra, Wigderson STOC'95], the paper that defined asymmetric communication complexity.

Without disparaging this great paper, I must say that the presentation is awful. The authors fail to realize the vast conceptual contributions that their asymmetric communication model can make. Think of the implications to understanding social interactions between humans (potentially, we may finally understand communication inside a marriage!). Instead, the authors chose to concentrate on boring technical aspects, like showing that their concept can prove lower bounds for computational problems.

To prove lower bounds for set disjointness, we are going to look carefully at the truth table of the function. This is a gigantic object, a 2D array with (u choose n) rows (corresponding to Alice's possible inputs), and (u choose m) columns (corresponding to Bob's inputs). Every entry is 1 if the set described by the column is disjoint from the set described by the row, and 0 otherwise.

The starting point of most communication lower bounds is the concept of (combinatorial) rectangles. A rectangle is a matrix minor of the truth table, i.e. a set AxB, where A is a subset of the rows and B is a subset of the columns. [Warning: this does not look like a rectangle in the geometric sense, since the rows in A and columns in B may not be consecutive.]

Suppose you are an outside observer, who doesn't know the inputs of Alice and Bob, but watches the communication taking places and tries to guess the inputs. After seeing some transcript of the communication, what have you learned about the input? It turns out, the possible problem instances that lead to a fixed communication trascript are always a combinatorial rectangle!

This can be seen by induction on the communication protocol. Before any communication, any inputs look plausible to the outside observer, i.e. the plausible inputs are the the entire truth table matrix. Say that in the next step, Alice sends a bit. This breaks the plausible inputs of Alice in 2 disjoint classes: the inputs for which she would send a 1, and the inputs for which she would send a 0. Observing the bit she sent, your belief about the input changes to a subset for Alice, and does not change in any way for Bob. Thus, your belief changes to a subrectangle, that drops some of the rows of the old rectangle. By analogous reasoning, when Bob sends a bit, your belief changes by dropping some columns.

Communication lower bounds follow by proving two facts:

1. If the communication protocol is short, the rectangle reached at the end is "large". (Intuitively, there weren't many steps of the induction to shrink it.) But in the final rectangle, all entries must be identical, either zero or one, because the protocol finishes by announcing the answer to the problem. In other words, if the protocol finished by announcing an answer, and there's still a plausible input for which the answer is different, the protocol is sometimes wrong.
   
   
2. Combinatorially, one shows that any large rectangle is bichromatic (contains both zeros and ones).
   

We are now going to show lower bounds for set disjointness, implementing these 2 steps.

1: Richness and large rectangles. How do we prove a useful result saying that the final rectangle must be "large"? For this, [MNSW] introduce the notion of "richness" (I don't know the story behind the name). We say (the truth table of) a function is [U,V]-rich if it contains at least V columns, each of which has at least U one-entries.

Lemma: If Alice and Bob compute a [U,V]-rich function by communicating a total of a, respectively b bits, the function contains a rectangle of size (U/2^a) x (V/2^a+b) with only one entries.

Proof: By induction on the length of the protocol. Let's say that we are currently in a rectangle AxB that is [U,V]-rich. We have two cases:

• Bob communicates the next bit. Let's say B₀ is the set of columns for which he sends zero, and B₁ is the set for which he sends one. Since AxB contains V columns with at least U ones, either AxB₀ or AxB₁ contain V/2 columns with at least U ones. We continue the induction in the [U,V/2]-rich rectangle.
  
  
• Alice communicates the next bit, breaking A into A₀ and A₁. Each of the V columns that made AxB rich has at least U/2 ones in either A₀xB or A₁xB. Thus, in either A₀xB or A₁xB we have find at least V/2 columns that have at least U/2 ones. We can continue the induction in a rectangle that is [U/2, V/2]-rich.
  

At the end of the protocol, we reach a monochromatic rectangle that is [U/2^a, V/2^a+b]-rich. Since the rectangle has nonzero richness, it contains some ones, and therefore it contains only ones. Furthermore, it must have size at least U/2^a by V/2^a+b to accomodate the richness.


2: Rectangles in set disjointness. Remember that we are interested in the case of a dense T; let's assume m=u/2 for concreteness. A column of the truth table is a set T of m=u/2 elements from the universe [u]. For each T, there are (u/2 choose n) sets S which are disjoint from T. Thus, the problem is [(u/2 choose n), (u choose u/2)]-rich. By the richness lemma, we obtain a one-rectangle of size (u/2 choose n) / 2^a by (u choose u/2) /2^a+b.

Assume we have a rectangle {S₁, S₂, ...} x { T₁, T₂, ...} that is all ones. Then, evey S_i is disjoint from every T_j. Defining S'= S₁ ∪ S₂ ∪ ... and T'= T₁ ∪ T₂ ∪ ..., it must be that S' is disjoint from T', therefore

(1) |S'| + |T'| ≤ u.

But also, the size of the rectangle is at most (|S'| choose n) by (|T'| choose u/2), because every row is an n-subset of S', and every column an m-subset of T'. Therefore:

(2) (|S'| choose n) ≥ (u/2 choose n) / 2^a
(3) (|T'| choose u/2) ≥ (u choose u/2) / 2^a+b

We now pull the following binomial inequality out of our hat:

(A choose C) / (B choose C) ≥ (A/B)^C

Then (2) becomes (u/(2|S'|))ⁿ < 2^a, and thus |S'| > u / 2^O(a/n). From (1) we have |T'| ≤ u - |S'| ≤ u (1 - 2^-O(a/n)). Applying the binomial inequality to (3), we have:

(u / |T'|)^u/2 ≤ 2^a+b => (1+2^-O(a/n))^Θ(u) ≤ 2^a+b => e^u/2O(a/n) ≤ 2^a+b => b ≥ u / 2^O(a/n), QED.

The first implication used 1 / (1 - ε) > 1 + ε. The second implication used (1 + 1/A)^B = ((1 + 1/A)^A)^B/A = e^Θ(B/A).