Maximum Overhang

Year of Award: 2011

Award: Robbins

Publication Information: American Mathematical Monthly Vol. 116, November 2009, pp. 763-787.

Summary (From the January 2011 Prizes and Awards booklet): This paper is a sequel to the paper Overhang published in the American Mathematical Monthly, vol. 116, January 2009, pp. 19-44. In that paper the authors showed that \(n\) blocks can be stacked using suitable counterbalancing to achieve an overhang proportional to \(n^{1/3}\). In this paper the authors give a complementary argument showing that an overhang proportional to \(n^{1/3}\) is, in fact, the largest possible for any balanced stack.

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.

Yuval Peres is currently the manager of the Theory Group at Microsoft Research, Redmond, Washington, and is also affiliated with the University of Washington and the University of California, Berkeley. Yuval received his Ph.D. from the Hebrew University, Jerusalem, in 1990. He has taught at Stanford, at Yale, and in Jerusalem, and he was a professor at UC Berkeley until 2006. He is a recipient of the Rollo Davidson and Loeve prizes and was an invited speaker at the Inter­national Congress of Mathematicians in Beijing, 2002. Yuval works on random walks, Brownian motion, mixing of Markov chains, Hausdorff dimension, percola­tion, random spanning trees, point processes, and random analytic functions. His favorite quote is from his son Alon, who was overheard at age 6 asking a friend: "Leo, do you have a religion? You know, a religion, like Christian, or Jewish, or Mathematics...?"

Mikkel Thorup has a D.Phil. from Oxford University, 1993. From 1993 to 1998 he was at the University of Copenhagen. Since then he has been at AT&T Labs—Research. He is also a Fellow of the Association for Computing Machinery (ACM) and a member of the Royal Danish Academy of Sciences and Letters. His main work is in algorithms and data structures, and he is the editor of this area for the Journal of the ACM. One of his best-known results is a linear-time algorithm for the single-source shortest paths problem in undirected graphs. Mikkel prefers to seek his mathematical inspiration in nature, combining the quest with his hobbies of bird watching and mushroom picking.

Peter Winkler is a professor of mathematics and computer science and the Albert Bradley Third Century Professor in the Sciences at Dartmouth College. Winkler's mathematical research is primarily in combinatorics, probability, statistical physics, and the theory of computing. He holds a dozen patents in cryptology, holography, distributed computing, optical networking, and marine navigation. He is the author of two collections of mathematical puzzles, a portfolio of compositions for ragtime piano, and (just published) a book on cryptologic methods in the game of bridge.

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 Tech­nology, and his M.Sc. and Ph.D. in computer science from Tel Aviv University. His main research interests are algorithms and complexity, combinatorial opti­mization, 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.