Suresh describes two of the nicest talks at SODA today: Rakesh Vohra's fascinating account of how to accurately predict the past (sic), and Seshadri Comandur's talk on self-improving algorithms. But in my opinion the nicest—or at least the sillest—talk of the day was by Uri Zwick.
Suppose we have a set of n SODA proceedings that we'd like to stack on the edge of a table, so that the stack reaches as far past the edge of the table as possible. How much overhang can we get? To keep the problem somewhat tractable, let's restrict the problem to two dimensions and pretend the proceedings are long, thin, frictionless, horizontal rectangles.
Anyone who's had a discrete math class has seen a way to stack the books so that the top book hangs out Θ(log n) book-lengths from the edge of the table.
This harmonic construction is often implicitly assumed to be the best possible, but that's only true if the books are stacked one on top of the other. If more than one book can rest on another book, it is possible to get more overhang from the same number of books. But just how much?
Mike Paterson and Uri Zwick described the following simple “brick wall” construction. For any positive integer k, a k-slab is a portion of a brick wall with 2k-1 rows, alternating between k-1 and k bricks long. For example, a 1-slab is a single row of two bricks; a 2-slab is a row of 3, a row of 2, and a row of 3. A 0-stack is a single brick, and for any positive integer k, a k-stack is a k-slab on top of a (k-1)-stack. A k-stack contains Θ(k^3) bricks and has overhang (k+1)/2. In other words, with n bricks, this construction achieves an overhang of Ω(n1/3)—exponentially more than the harmonic stack!
It's not immediately obvious that every k-stack is stable, but Paterson and Zwick give a nice inductive proof. More generally, they show that it is possible to automaticlaly check whether any given stack of books is stable, by checking whether a certain related linear program is feasible. At the end of his talk, Uri reported that he and several co-authors have proved that this construction is asymptotically optimal—the overhang of any stable stack of n books is at most O(n1/3)—but we'll have to wait for SODA 2007 to find out why.
In a fit of ironic justice, the talk was scheduled in the smallest of the three conference rooms. Despite crowding tight enough to give any fire marshal (or audience member) heart palpitations, Uri's audience overflowed several yards out into the hallway.
Now that is cool!
Posted by: Dave Bacon | January 23, 2006 at 01:06 PM