Seminar series
Date
Tue, 06 May 2008
14:30
14:30
Location
L3
Speaker
Mike Paterson
Organisation
Warwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^{1/3} is best possible, resolving the long-standing overhang problem up to a constant factor.
I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years.