Cool with a Gaussian: A Cubic Volume Algorithm
Tuesday, March 17, 2015 - 2:00pm - 2:40pm
Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes and exponential lower bounds for deterministic algorithms in the oracle model). We present a new algorithm, whose complexity grows as n^3 in the oracle model for any well-rounded convex body. The two main new components of this algorithm are more efficient Gaussian sampling and an accelerated cooling schedule. It improves upon the previous best algorithm of Lovász-Vempala from 2003 by a factor of n, and bypasses the famous KLS hyperplane conjecture, which appeared essential to achieving such complexity. We will also demonstrate an implementation based upon our algorithm in MATLAB.