The 6 Months News Cycle

The STOC accepted papers, with some pointers to online versions, can be found here. I had two papers: Towards Polynomial Lower Bounds for Dynamic Problems and Changing Base without Losing Space. More on them later.

The FOCS call for papers is here. An experimental feature is the lack of page limits. While nominally the reviewers are only obliged to look at the first 10 pages, we all know such formalism is irrelevant. Reviewers look at anywhere between 0.5 and 50 pages, until they form some opinion about the paper. As an author, I'm happy to stop playing the childish \baselinestretch and \appendix games, which were not helping anyone.

On the other hand, I vividly remember a discussion during my tenure on the FOCS PC when people made a strong case for a strict 10-page submission limit (no appendix). Many authors don't give a damn about teaching the reader anything, and seem driven by the desire to make their paper look as long and technical as possible. The reasoning was that a strict 10-page limit might actually force them to explain some ideas. Instead of a strict page limit, I would actually advocate using reviewers that are not easily intimidated, and stop accepting papers just because "it looks hard and these people seem to have put a lot of effort into it." In practice, of course, this ideal is hard to implement.

Forward by one conference, and I am on the SODA PC. This seems to be a standard punishment for having 4 papers in the conference. Speaking of which, I have recently uploaded slides for all these papers.

I am travelling to Europe in the coming weeks, so my series on hashing will continue at a slower pace.

Cuckoo Hashing

Today, we will prove bounds for the basic cuckoo hashing. We are going to place our n keys into two arrays A[1..b] and B[1..b], where b=2n. For this, we will use two hash functions, h and g. When some element x arrives, we first try to put it in A[h(x)]. If that location already contains some element y, try to move y to B[g(y)]. If that location already contains some z, try to move z to A[h(z)], and so on until you find a free spot.

The proper image to have in mind is that of a random bipartite graph. The graph will have b nodes on each side, corresponding to the locations of A and B. In this view, a key x is an edge from the left vertex h(x) to the right vertex g(x).

Simple paths. As a warm-up, let's deal with the case of simple paths: upon inserting x, the update path finds an empty spot without intersecting itself. It turns out that the update time of cuckoo hashing behaves like a geometric random variable:

The probability that insert(x) traverses a simple path of length k is 2^-Ω(k).

I will prove this by a cute encoding analysis (you know I like encoding proofs). Let's say you want to encode the two hash codes for each of the n keys. As the hash functions h and g are truly random, this requires H=2nlg b bits on average (the entropy). But what if, whenever some event E happened, I could encode the hash codes using H-Δ bits? This would prove that Pr[E]=O(2^-Δ): there are only O(2^H-Δ) bad outcomes that lead to event E, out of 2^H possible ones. Thus, the task of proving a probability upper bound becomes the task of designing an algorithm.

In our case, E={insert(x) traverses a simple path of length k} and we will achieve a saving of Δ=Ω(k). Here is what we put in the encoding:

• one bit, saying whether the path grows from A[h(x)] or B[g(x)];
  
• the value k, taking O(lg k) bits;
  
• all edges of the path, in order, taking (k-1)lg n bits.
  
• all vertices of the path, in order, taking (k+1)lg b bits.
  
• the hash codes for all keys not on the path, in order, taking (n-k)·2lg b bits.
  

Observe that the hash codes of the k keys on the path are specified using essentially half the information, since a hash code is shared between two edges. Since lg n = lg(b/2) = lg b - 1, the encoding saves Δ=k-O(lg k) bits compared to H.

The intuition for why a k-path occurs with probability 2^-Ω(k) is simple. Say I've reached edge y and I'm on the right side. Then, the probability that B[g(y)] is collision free is at least 1/2, since there are only n keys mapped to a space of 2n. In other words, at each point the path stops with probability half. This is exactly what the encoding is saying: we can save one bit per edge, since it takes lgn to encode an edge, but lg(2n) to encode an endpoint.

One cycle. Let us now deal with the case that the connected component of x contains one cycle. It is tempting to say that cuckoo hashing fails in this case, but it does not. Here is what might happen to the update path in case a cycle is part of the component (see figure):

1. the path luckily avoids the cycle and finds a free location without intersection itself. Cool.
   
2. the path reaches B[g(x)], which is occupied by some key y. Note that this has closed the cycle through the x edge, but the x edge is not actually traversed. Following y to A[h(y)] must eventually reach a free spot (no more cycles).
   
3. the path intersects itself. Then, it will start backtracking, flipping elements back to their position before Insert(x). Eventually, it reaches A[h(x)], where the algorithm had originally placed x. Following the normal cuckoo rules, x is moved to B[g(x)] and the exploration from there on must find an empty spot.

As before, we want to show that an update takes time k with probability 2^-Ω(k). In cases 1 and 2, we can simply apply the encoding from before, since the path is simple. In case 3, let ℓ be the number of edges until the path meets itself. The number of edges after B[g(x)] is at least k-2ℓ. Thus, we have a simple path from x of length max{ℓ, k-2ℓ} = Ω(k), so the old argument applies.

Two cycles. We now arrive at the cases when cuckoo hashing really fails: the bipartite graph contains as a subgraph (1) a cycles with a chord; or (2) two cycles connected by a path (possibly a trivial path, i.e. the cycles simply share a vertex).
From the figure we see that, by removing two edges, we can always turn the bad subgraph into two paths starting at x. We first encode those two paths as above, saving Ω(k), where k=size of the subgraph. Now we can add to the encoding the two infringing edges. For each, we can specify its identity with lg n bits, and its two end points with O(lg k) bits (a lower order loss compared to
the Ω(k) saving). In return, we know their two hash codes, which are worth 4lg b bits. Thus, the overall saving is at least 2lg n bits.

We have shown that an insertion fails with probability O(1/n²). By a union bound, cuckoo hashing will handle any fixed set of n elements with probability 1-O(1/n).

This bound is actually tight. Indeed, if three keys x,y,z have h(x)=h(y)=h(z) and g(x)=g(y)=g(z), then cuckoo hashing fails (this is the simplest obstruction subgraph). But such a bad event happens with probability (n choose 3)·b² / b⁶ = Θ(1/n).

Better Guarantees for Chaining and Linear Probing

Last time we showed that chaining and linear probing enjoy O(1) expected running times per operation. However, this guarantee is fairly weak, and certainly does not explain the popularity of the schemes. If you had a computation that was expected to run for 4 hours, would you be happy to hear, say, that it might take 10 hours with 10% probability?

Worst case w.h.p. So, what bound can be put on the running time that hold with high probability? For chaining, simply apply the Chernoff bound. Given that a bin contains μ=O(1) elements in expectation, the probability that it contain Z elements is at most e^Z-μ / (μ/Z)^Z = (O(1)/Z)^Z. To make this be n^-c, set Z=Θ(lg n/lglg n).

Observe that this bound is tight. There are (n choose Z) ≈ n^Z/Z! combinations of keys that can land in a designated bin, and some Z keys land there with probability b^-Z=(2n)^-Z. Thus, in expectation, at least one bin will see Z=Ω(lg n/lglg n) elements.

For linear probing, we can also reduce this to a balls-in-bins analysis, by defining a bin as L=O(lg n) consecutive locations in the array. In the running example b=2n, such a bin is full when Z=2μ=L. By Chernoff, this happens with probability e^Z-μ / (μ/Z)^Z = (e/4)^L/2. Thus, the maximal run in O(lg n) w.h.p. Again, this is tight by a direct calculation.


Amortized bounds. Unfortunately, these worst-case¹ bounds are not too satisfactory either, since O(lg n) is trivial to get by binary trees. If you grant me some lenience for my modeling, I will prove an O(1) amortized bound w.h.p., which I believe explains the power of the algorithms much better.

¹ There is an unfortunate tendency of some TCS papers to use "worst case" when they really mean deterministic. I am much happier with the convention that worst case is opposite of amortized, at least when your paper has any connection to data structures.

Formally, I will prove the following, rather trivial statement:

Let T≥clg n, for a large enough constant c. Any T operations in chaining hashtables only touch O(T) memory w.h.p.

Fix the hash codes of the T elements, and define our "bin" to consist of these ≤T distinct hash codes. All other elements are still totally random, and we expect μ≤Tn/b=Θ(lg n) to fall into the bin. If μ≤Z/(2e), the Chernoff bound is e^Z-μ/(μ/Z)^Z ≤ 2^-μ = high probability.

But does this actually mean that chaining has O(1) amortized running time? Formally, no: if I repeat a single query T times, the running time will be T times the running time of that query, i.e. a geometric random variable with no good concentration. Here is where I invoke a bit of lenience in my modeling: in practice, it is ridiculous to worry about repeating one of the last O(lg n) operations! The memory used by these recent updates will be fresh in the first level of cache, making a repetition cost essentially zero. (One may formally say that chaining has amortized O(1) running time w.h.p. in the external memory model with a cache of size Ω(lg n).)

A pretty way to understand the amortized bound is as a "buffer size" guarantee. The most demanding applications of hashtables are in analyzing a continuous stream of data, when operations need to be super-fast to keep up with the line speed. In such application, if the design is at all sensible, there will be a buffer between the network interface and our CPU. The goal is not necessarily to take O(1) time for every single operation, but to keep the buffer small. Our proof says that the buffer will not grow to more than T=O(lg n) w.h.p., if you can afford the average time/operation.

For linear probing, we can instead show:

Let T=Ω(lg³n). Any T operations in chaining hashtables only touch O(T) memory w.h.p.

Remember from last time that we analyzed linear probing by building a binary tree over the array, and bounding the number of nodes that become dangerous (two-thirds full).

Let μ be the number of keys we expect under some node. First of all, if μ≫lg n, we do not need to worry about the node: it doesn't become dangerous w.h.p. Otherwise, we showed that the node becomes dangerous with probability O(1/μ²); if it does, we will pay a cost of μ.

Looking at T elements, I am dealing with ≤T nodes on each level, and I expect O(T/μ²) nodes to be dangerous. As long as T/μ² ≥ clg n, Chernoff tells me that only O(T/μ²) nodes are dangerous w.h.p. Since we only deal with μ=O(lg n), I needed to set T=Ω(lg³n). With this bound, the number of memory locations accessed by the T operations is Σ_μ=2^i O(T/μ²)·μ = O(T) w.h.p.

I end with a question to my knowledgeable readers. By being more careful, I can prove T=Ω(lg^1+εn) suffices for linear probing. Is it possible to prove T=Ω(lg n), as in chaining? (Perhaps I'm missing something obvious.)

Basic Hashtables

To understand the state of the art in hash tables, you must understand the holy trinity of the area: chaining, linear probing, and cuckoo hashing. Chaining is the one that amateurs know, and shows up frequently in code. Linear probing is what you use when performance really matters. And cuckoo hashing is the theoretician's darling, providing the playground for a constant stream of papers.

Here is a basic description of the three hash tables, if you don't know them. There are, of course, many variations.

chaining

Each item x is hashed to one of b bins, where b=Ω(n). Each bin is stored as a linked list, with pointers to the head of each list stored in an array A[1..b]. In practice, you would store the head of each list in A[i], to save a pointer and a cache miss.

linear probing

We hold an array A[1..b] of records, where b ≥ (1+ε)n. When inserting x, we try to place it at A[h(x)]; if that location is empty, try A[h(x)+1], A[h(x)+2], ..., until you find an empty location. This addresses the main performance issues of chaining: there are no cache misses (we walk a contiguous region, not a linked list), and the space is better (no pointers). But, intuitively, it demands much more robustness from the hash function: now some elements hashing to location k can interfere negatively with elements hashing to a close k'.

cuckoo hashing

We hold two arrays A[1..b] and B[1..b] and use two hash functions, h and g. When x arrives, we try to put it at A[h(x)]. If that location already contains y, try to move y to B[g(y)]. If that location already contains z, try to move z to A[h(z)], and so on until you find a free spot. Observe that the query for x is worst-case constant time: just look for x in A[h(x)] and B[g(x)]!

Let us assume, for now, that hash functions are truly random. Moment bounds, which I discussed last time, are useful for understanding both chaining and linear probing (see below). For cuckoo hashing, the analysis is quite different.

Chaining. It is trivial to argue that the expected running time of insertions
and deletions is constant. Focus on some element q. For i≠q, let X_i be the indicator that h(i)=h(q). Then, the time it takes to insert or query q is O(1 + ΣX_i).

Therefore, the expected time is bounded by E[ΣX_i] = ΣE[X_i] = n/b = O(1), since h(x)=h(i) only happens with probability 1/b.

What we have just argued is that the expected number of elements that collide with x is O(1). Another way to state this is that the variance of a bin's size is O(1), a fact that we proved last time. To see this connection, let B_i be the number of elements in bin i. Observe that:

E[Σ(B_i)²] = n + E[#colliding pairs] = n + n · E[#elements colliding with x] = n + n²/b

By uniformity of the hash function, E[(B_i)²] = n/b + n²/b². We have obtained the variance: Var[B_i] = E[(B_i)²] - E[B_i]² = n/b.


Perfect hashing. A very cool consequence of this variance analysis is the well-known dictionary of [Fredman, Komlós, Szemerédi FOCS'82]. Their idea was to construct a static dictionary using randomization, but then have the query be completely deterministic. (Later work has focused on obtaining deterministic queries even in dynamic dictionaries, as in cuckoo hashing, and on completely eliminating randomness.)

The basic idea is that, if we had space 2n², perfect static dictionaries would be trivial. Indeed, the expected number of collisions is n² / b = 1/2, so, by Markov, the hash function is collision-free with probability at least 1/2. For the construction, we can simply generate hash functions until we see a perfect one (a constant number of iterations, in expectation).

To bring the space down to O(n), remember that our variance analysis showed E[Σ(B_i)²] = O(n). Thus, instead of storing the items mapping to A[i] as a linked list, we should store a mini-hashtable of quadratic size inside each A[i]. These mini-tables provide perfect hashing, but their total size is just linear!


Linear probing. The relevance of moments to linear probing was only recognized in a recent breakthrough paper [Pagh, Pagh, Ruzic STOC'07]. I will show the analysis for b=3n to ease notation; it is easy to extend to any load.

In true data-structures style, we consider a perfect binary tree spanning the array A[1..b]. A node on level k has 2^k array positions under it, and (1/3)·2^k items were originally hashed to them in expectation. (Here I am counting the original location h(x) of x, not where x really appears, which may be h(x)+1, h(x)+2, ...). Call the node "dangerous" if at least (2/3)·2^k elements hashed to it.

Now say that we are dealing with element q (a query or an update). We must bound the contiguous run of elements that contain the position h(q). The key observation is that, if this run contains between 2^k and 2^k+1 elements, either the ancestor of h(q) at level k-2 is dangerous, or one of its siblings in an O(1) neighborhood is dangerous.

Let's say this run goes from A[i] to A[j], i≤h(q)≤j. The interval [i,j] is spanned by 4—9 nodes on level k-2. Assume for contradiction that none are dangerous. The first node, which is not completely contained in the interval, contributes less than (2/3)·2^k-2 elements to the run (it the most extreme case, this many elements hashed to the last location of that node). But the next nodes all have more than 2^k-2/3 free locations in their subtree, so 2 more nodes absorb all excess elements. Thus, the run cannot go on for 4 nodes, contradiction.

Now, the expected running time of an operation is clearly:

Σ_k O(2^k)·Pr[h(q) is in a run of 2^k to 2^k+1 elements].

As argued above, this probability is at most O(1) times the probability that a designated node at level k-2 is dangerous.

The rest is a simple balls-in-bins analysis: we want the probability that a bin, of expected size μ=2^k-2/3, actually contains 2μ elements. Last time, we showed that Chebyshev bounds this probability by O(1/μ). Unfortunately, this is not enough, since Σ_k 2^k·O(1/2^k-2) = O(lg n).

However, if we go to the 4th moment, we obtain a probability bound of O(1/μ²). In this case, the running time is Σ_k2^k·O(1/2^2(k-2)) = Σ O(2^-k) = O(1). So the 4th moment is enough to make this series decay geometrically.

Moments

This post is a fairly basic review of common probability notions. Things will get more interesting in future posts. Somebody who wants to do TCS but has not studied probability yet can read this post carefully and reach about the same level of formal training that I've had :)


Say we distribute n items into b bins randomly. Fixing our attention on one bin (e.g. the first), how can be bound the number of items landing there?

The expected number of items is n/b. Thus, by the Markov bound, we get:

Pr[bin contains ≥ 2n/b items] ≤ 1/2

Variance. To strengthen the bound, we may look at the variance and apply the Chebyshev bound. Let X be the number of elements in the first bin. Also let μ=E[X]=n/b. The variance of X is defined as E[(X-μ)²], and this is exactly what we need to compute for Chebyshev.

How can we compute the variance? We let X_i be the indicator for whether the i-th item falls in our bin (indicator means the variable is 1 if the event happens, and 1 otherwise). Then, X=X₁+...+X_n.

Since we are interested in X-μ, not X, it is more convenient to define Y_i = X_i-(1/b). With this definition, X-μ=Y₁+...+Y_n. Observe that E[Y_i] = 0.

We can not break up the variance:

Var[X] = E[(X-μ)²] = E[( ΣY_i )²] = Σ E[Y_iY_j]

We are down to analyzing E[Y_iY_j], which is simple. If i≠j, Y_i and Y_j are independent random variables. Thus, the expectation commutes with the product:

E[Y_iY_j] = E[Y_i] E[Y_j] = 0

In the case i=j, we use brute force calculation. Y_i=-1/b with probability 1-(1/b), and equals 1-(1/b) with probability 1/b. Thus, E[(Y_i)²] = O(1/b).

We have found the variance to be E[(X-μ)²]=O(n/b)=O(μ). Then:

Pr[X ≥ 2n/b] = Pr[X-μ ≥ μ] ≤ Pr[(X-μ)² ≥ μ²] ≤ O(μ) / μ² = O(1/μ)

Observe that the Chebyshev bound is nothing more than Markov on the variable (X-μ)².

Third moment. If stronger bounds are required, we can try to look at higher moments, E[(X-μ)^k]. Unfortunately, moving to the 3rd moment (or any other odd moment) does not really help: the variable (X-μ)³ is no longer positive, so Markov cannot apply.

One way to fix this is to look at the absolute third moment: E[|X-μ|³]. It is no longer easy to compute this moment, since we cannot break up |ΣY_i|³ into components, due to the absolute value. Thus, we do not commonly use absolute moments.

However, I have come across absolute moments once, in the following interesting application. The central limit theorem states that the average of N i.i.d. variables tends to the normal distribution as N→∞. The Berry-Esseen theorem quantifies this phenomenon: it gives a fairly strong bound on the speed of the convergence, assuming the third absolute moment of the summands is bounded.

Fourth moment. To strengthen the variance bound, one most commonly looks at the 4th moment. To get a feeling for it, let's see how we can bound the 4th moment in the balls and bins case:

E[(X-μ)⁴] = E[( ΣY_i )⁴] = Σ_ijkl E[ Y_iY_jY_kY_l ]

We can understand the terms generated by an (i,j,k,l) tuple by case analysis:

1. If one of the elements appears exactly once, the term is zero. For instance, let's say i∉ {j,k,l}. Then Y_i is independent of the rest, so the expectation commutes with product: E[Y_iY_jY_kY_l] = E[Y_i] E[Y_jY_kY_l] = 0.
   
   
2. If all elements are equal (i=j=k=l), E[(Y_i)⁴] = O(1/b).
   
   
3. If the tuple consists of two equal pairs, for instance (i,i,j,j), we have E[(Y_i)² (Y_j)²] = E[(Y_i)²] E[(Y_j)²] = O(1/b²).

We have n terms of type 2, and O(n²) terms of type 3. Thus, the fourth moment is O(n² / b²) = O(μ²).

To bound the bin size, we can now apply Markov on the fourth moment:

Pr[X ≥ 2n/b] = Pr[X-μ ≥ μ] ≤ Pr[(X-μ)⁴ ≥ μ⁴] ≤ O(μ²) / μ⁴ = O(1/μ²)

Thus, our bounds have improved from 1/2 for Markov, to O(1/μ) for Chebyshev, and to O(1/μ²) for the 4th moment. Going to the 6th, 8th, etc yields the predictable improvement.

Chernoff. The next step to improving our bounds is to go to the Chernoff bound. This bound has many forms, in particular two rather different instantiations for additive and relative error.

Let me quote an uncommon, but nifty version of the theorem:

Let X₁, ..., X_n be independent random variables bounded in [0,1]. Let X=ΣX_i and μ=E[X].

If Z≥μ, then Pr[X≥Z] ≤ e^Z-μ (μ/Z)^Z.

If Z≤μ, then Pr[X≤Z] ≤ e^Z-μ (μ/Z)^Z.

In our case, we are interested in Z=2μ. Thus, the upper bound on the probability is e^μ / 2^2μ ≈ 1 / 1.47^μ. We have obtained an exponential bound, instead of the polynomial bound possible by constant moments.

If we have been interested in showing that the bin gets at least Z=μ/2 elements, the second part of the theorem gives a probability bound of e^-μ/2 2^μ/2 ≈ 1 / 1.17^μ. Note how the two terms of the bound trade places: e^Z-μ is pushing the probability down in the second case, while (μ/Z)^Z is making sure it is small in the first case.

The proof of Chernoff is a bit technical, but conceptually easy. As before, we define Y_i = X_i - E[X_i], so that X-μ=ΣY_i. Instead of looking at E[(X-μ)^k], we will not look at E[α^X-μ] (where α>1 is a parameter than can be optimized at the end). This quantity is easy to compute since E[α^ΣYi] = E[Π α^Yi] = Π E[α^Yi]. At the end, we can just apply Markov on the positive variable α^X-μ.

High probability. In TCS, we are passionate about bounds that hold "with high probability" (w.h.p.), which means probability 1 - 1/n^c, for any constant c. For instance,

Algorithm A runs in O(n) time w.h.p.

formally means the following:

There exists a function f(.) such that, if you choose any constant c, I can prove that algorithm A runs in time f(c)·n with probability 1 - 1/n^c.

While such bounds may seem weird at first, they do make a lot of sense: think of applying some randomized procedure a polynomial number of times. Also, these bounds make a lot more sense when dealing with many experiments over huge data sets (the essence of Computer Science) than adopting the convention from statistics, which asks for bounds that hold with 95% probability.

Since we are usually happy with whp bounds, one often hears that Chernoff is morally equivalent to O(lg n)-moments. Indeed, such a moment will give us a bound of the form 1/μ^{O(lg n)}, which is high probability even in the hardest case when μ is a constant.

The paper of [Schmidt, Siegel, Srinivasan SODA'93] is often cited for this. Their Theorem 5 shows that you can get the same bounds as Chernoff (up to constants) if you look at a high enough moment.

Applications

This is the time when many young people are fretting about their applications, be they for undergrad admission, PhD admission, or academic jobs. (At the same time, marginally older people are happy to be done with recommendation letters.)

First of all, I wanted to suggest that you channel the energy (or, should I say, agitation) of this moment into positive directions. My interview spring was also when I came up with some pretty neat ideas and wrote 4 FOCS papers.

Second of all, I wanted to share an anecdote that I heard during my job hunt, which may or may not help. As the story goes, a department chair comes back after the break and finds a couple of hundred applications sitting on his desk. He looks at the pile, shakes his head, and promptly commits half of them to the recycle bin. He then announces that, "This university does not need unlucky people."

If you doubt that this could be true, let me offer statistical evidence from my wife's hospital: on her year, the doctors that got jobs were Maria, Miriam, Mariam, and Milos. (Evidently, the secretary had sorted the pile before putting it on the chair's desk.)

Amusingly, their workplace also offers the best illustration of a hash function collision that I have yet seen. They have three Romanian doctors which go by Mira, Mira, and Mera (hash codes for Mirabela, Miriam, and Merima -- all exceedingly rare names in Romania).

Blog happenings

As you may have noticed, this blog has been on a bit of a hiatus. On the one hand, my expectations for politics-by-blog have decreased to a minimum and my boredom with the theory community has grown. On the other hand, I have not had enough time for exposition-by-blog --- or, better said, I discovered that my thought process is too obsessive and erratic to leave room for regular expository interruptions.

In an attempt to pull myself from the blog hiatus, let me respond to two recent blog posts, one guest post by Mikkel on My Biased Coin, and one post by Lipton.

My own view of Mikkel's post reads like: "Hey, remember that big-big fuss from 1-2 years ago about simplicity as a virtue? How come this was hijacked by people wanting to introduce new models all the time, and didn't help the papers on real algorithmic problems, where simplicity matters the most? Do we need to start our own «Innovations in Real Computer Science» conference, or can we have a session at SODA instead? "

My own favorite example of a book algorithm is the "mod-3" suffix tree construction of [Kärkkäinen, Sanders ICALP'03]. This is an amazingly simple algorithm (much simpler than anything before), and truly feels like the "ultimate" algorithm for suffix tree construction. It also demonstrates a rare property: dividing into 3 parts in a recursive construction can work much better than dividing into 2. This algorithm should (and probably will) be in any Intro to Algorithms course.

So, was this algorithm the Best Paper in STOC/FOCS? Not nearly --- in fact most STOC/FOCS people probably never heard of it. I also know from inside sources that the paper was viewed as somewhat borderline at ICALP (which is not too surprising --- as screwed up as US conferences are, we still don't compare to the European ones).

***

Moving on to Lipton's blog, we notice that most discussion is confused by the difference between running time and some (problem-dependent) optimization function.

Some people claim that they are different because of Moore's law (your slower algorithm will be fast enough soon), or the fact that CPU cost is not as real as, say, the cost of shipping goods around by trucks in your optimization problem. I disagree with both of these views.

It's irrelevant if Moore's law will make your algorithm fast enough in 2 years; by then, the competition may make you bankrupt. And if you really believe in thinking long term, you should probably be working on quantum computers and worrying about the speed of light (we all know that a memory of N bits has diameter at least N^1/3, so memory accesses cannot be "constant time"). Sure, you may not say anything relevant for 50+ years, but then you will finally be avenged --- and you may be as influential as Babbage's computer was in the design of Java. My response to this long run thinking is a well-known quote from economics: "People don't eat in the long run." (Harry Hopkins)

How "real" CPU cost is will vary. If you're compressing Google's logs by 10%, you're likely to save 10% of a pretty big cost, a worthy goal. In time-constrained systems (like ATT routers), this cost is not smooth, but exhibits a phase transition. If you make this algorithm 30% faster, we can provide this extra functionality that competitors don't have, and convince some companies to switch to our network. If not, not. Adding 30% more computing power is essentially not an option.

So, no, the difference between running times and other optimization criteria is not that it is less of a cost. The difference is that we understand running times a whole lot better. Look, we spent decades understanding the usefulness and the shortcomings of asymptotic analysis, refining our computer model (Word RAM + external memory issues), etc. When we talk about running time, we usually know what we're talking about.

On the other hand, every combinatorial optimization problem is a modelling challenge. Constraints are not quite like this, the graph is not quite general, this cost function is not quite right etc etc. Each important problem needs (and deserves) considerable modelling work before our theoretical predictions are as good as we may want.

But what do we do at STOC/FOCS? We model the problem in the simplest way, ignoring applications (which we are largely unaware of). Then, we prove Θ(lg n) approximation bounds (complete with PCP lower bounds) for the dollar cost of shipping goods by trucks (a problem now rebranded with a fancy name). Now just wait for those Amazon guys to come asking about how to improve their 5% approximation, and we can tell them the problem is perfectly understood!

Basically, a lower bound greater than 2 on a dollar cost is a formal proof that your formalization of the problem is wrong.

So, should we get our hands really dirty and look at the problems in such detail? I think if you're going to be passionate about approximation algorithms, you should do it at least a few times. (I, for one, did a lot of performance-oriented programming before my current work on theory of running times...)

I hope that if our approximation algorithms community gets a lot closer to the OR community, good things will happen. On the one hand, they might give us a break with their "understanding the nature of computation" claims, when they realize they have only a vague idea of what computation really is. On the other hand, nice theory might yet be developed which will talk about 3% improvements...