Date: Tuesday, October 13, 2015
Title: Gaussian Cooling and Randomized Volume Computation
Abstract: Computing the volume of a convex body in ndimensional space is an ancient, basic and difficult problem (#Phard for explicit polytopes; requires exponential time for deterministic algorithms in the oracle model). We begin with a review of the progress made in the quartercentury 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 wellrounded convex body (any body can be rounded by an affine transformation). This improves the previous best LoVe 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
