Title:	Overhang
Date:	September 28, 2007 (Friday)
Time:	3:00 p.m. - 4:00 p.m.
Venue:	Room 121, 1/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker:	Professor Uri Zwick Tel Aviv University Israel

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.

Enquiries: Miss Temmy So at tel 2609 8444

For more information, please refer to http://www.cse.cuhk.edu.hk/seminar