Abstract :

How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This solution is widely believed to be optimal. We show, however, that it is exponentially far from optimal by giving explicit constructions with an overhang of Omega(n^{1/3}). Together with Yuval Peres, Mikkel Thorup and Peter Winkler, we have recently shown that no larger overhangs are achievable.

Joint work with Mike Paterson.

Biography:

Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He his currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.