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

Ben Cousins, Santosh Vempala

We present an $O^{\ast }(n^3)$ 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^…