# Cool with a Gaussian: an $$O^*(n^3)$$ volume algorithm

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$$ 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 KLS hyperplane conjecture, which appeared essential to achieving such complexity. En route, we'll review the progress made in the quarter-century since Dyer, Frieze and Kannan's breakthrough $$n^{23}$$ algorithm, and highlight some nice connections to probability and geometry.

### Affiliation

Georgia Institute of Technology

Santosh Vempala