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

 Computer Science/Discrete Mathematics Seminar I Topic: Cool with a Gaussian: an $O^*(n^3)$ volume algorithm Speaker: Santosh Vempala Affiliation: Georgia Institute of Technology Date: Monday, October 13 Time/Room: 11:15am - 12:15pm/West Bldg. Lect. Hall Video Link: http://video.ias.edu/csdm/2014/1013-SantoshVempala

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.