Computer Science/Discrete Mathematics Seminar I

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.