Tel-Aviv University - Computer Science Colloquium

Sunday, April 2, 2006, 11:15-12:15

Room 309
Schreiber Building

--------------------------------------------------------------------------------

Uri Zwick

Tel Aviv University

Title:

Overhang

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}). We also prove some

upper bounds on the overhang that can be achieved.

Joint work with Mike Paterson