Event Title: OR
Speaker Last Name:    OR
Year: (yyyy)

Mathematics Colloquium


Date:  Tuesday, October 13, 2015

Title:  Gaussian Cooling and Randomized Volume Computation

Abstract:  Computing the volume of a convex body in n-dimensional space is an ancient, basic and difficult problem (#P-hard for explicit polytopes; requires exponential time for deterministic algorithms in the oracle model). We begin with a review of the progress made in the quarter-century since Dyer, Frieze and Kannana's breakthrough n23 probabilistic algorithm, highlighting connections to probability and geometry. We then present a new algorithm (joint work with Ben Cousins), whose complexity grows as n3 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 hyperplane conjecture, which was originally introduced to improve volume algorithms and appeared essential to achieving this complexity.

Speaker:  Santosh Vempala
Institution:  Georgia Institute of Technology


Back to current Colloquium List
Back to UM Math seminars page


Department of Mathematics   |   2074 East Hall   |  530 Church Street  
Ann Arbor, MI 48109-1043
Phone: 734.764-0335   |   Fax: 734.763-0937

The page last modified
Site errors should be directed to