|Date: Tuesday, October 13, 2015
Title: Gaussian Cooling and Randomized Volume Computation
Abstract: Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes; requires exponential time for deterministic algorithms in the oracle model). We begin with a review of the progress made in the quarter-century since Dyer, Frieze and Kannana's breakthrough n23 probabilistic algorithm, highlighting connections to probability and geometry. We then present a new algorithm (joint work with Ben Cousins), whose complexity grows as n3 for any well-rounded convex body (any body can be rounded by an affine transformation). This improves the previous best Lo-Ve algorithm from 2003 by a factor of n, and bypasses the famous hyperplane conjecture, which was originally introduced to improve volume algorithms and appeared essential to achieving this complexity.
Speaker: Santosh Vempala
Institution: Georgia Institute of Technology