Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume

We present an O^*(n3) randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of O^*(n4). The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving this asymptotic complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. We also obtain an O^*(n3) randomized algorithm for integrating a standard Gaussian distribution over an arbitrary convex set containing the unit ball. Both the volume and Gaussian volume algorithms use an improved algorithm for sampling a Gaussian distribution restricted to a convex body. In this latter setting, as we show, the KLS conjecture holds and for a spherical Gaussian distribution with variance σ2, the sampling complexity is O^*(maxn3, σ2n2) for the first sample and O^*(maxn2, σ2n2) for every subsequent sample.