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.