NBIA Colloquium by Mikkel Thorup on the stacking problem

What is the Maximum Overhang for a Stack of n Blocks?

Mikkel Thorup
(Department of Computer Science, U. of Copenhagen)
How far can a stack of n identical unit-length blocks be made to hang over the edge of a table?  This basic question has a long history, appearing in physics and engineering textbooks at least as early as the mid-19th century. The answer was widely believed to be of order log n. Recently, Paterson and Zwick constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. We review their construction, and show here that order n^{1/3} is indeed best possible, thus resolving the long-standing overhang problem up to a constant factor.
(Joint work with Mike Paterson, Yuval Peres, Peter Winkler, and Uri Zwick.)

Mikkel Thorup is Professor at the University of Copenhagen and Head of Center for Efficient Algorithms and Data Structures (EADS). He received his D.Phil. degree from Oxford University in 1993. From 1993 to 1998 he was at the University of Copenhagen and from 1998 to 2013 he was at AT&T Labs-Research. He is an international authority in the area of algorithms and data structures and has received a number of awards for his work, including the 2015 Villum Kann Rasmussen Award for Technical and Scientific Research, Denmark's biggest individual prize for research.


All are welcome!  Refreshments will be served in the NBIA lounge after the talk.