You are here

Overhang

by Mike Paterson (Warwick University) and Uri Zwick (Tel Aviv University)

Year of Award: 2011

Award: Robbins

Publication Information: American Mathematical Monthly Vol. 116, January 2009, pp. 19-44

Summary: This paper proves the surprising result that \(n\) blocks can be (cunningly) stacked using suitable counterbalancing to achieve an overhang proportional to \(n^{1/3}\). (Many people have assumed that the overhang of about log \(n\), given by the standard calculus exercise, is optimal.)

Read the Article:

About the Authors (From the January 2011 Prizes and Awards booklet)

Mike Paterson is emeritus professor of Computer Science at Warwick University in the United Kingdom and is a Fellow of the Royal Society. His B.Sc. and Ph.D. in mathematics are from Cambridge University. Paterson started his teaching career at Massachusetts Institute of Technology and continued at Warwick where he has remained for nearly forty years. He was president of the Trinity Math­ematical Society as a student and of the European Association for Theoretical Computer Science somewhat later. He co-invented "Sprouts" with John Conway and received the Dijkstra Award in Distributed Computing. His interests have been mainly in algorithmic complexity, beginning from his early years at MIT, but have extended broadly within that area to include distributed algorithms, algorithmic game theory and, of course, the work recognised by this award.

Uri Zwick is a professor of Computer Science at Tel Aviv University, Israel. He received his B.Sc. in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and PhD in Computer Science from Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics. Zwick spent two years as a PostDoc at Warwick University after completing his Ph.D. and has been collaborating with Mike Paterson ever since.

Subject classification(s): Discrete Mathematics
Publication Date: 
Friday, January 21, 2011