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.