Mathematical Sciences Research Institute

Home » GFA Young Researchers Seminar: Efficient High-Dimensional Sampling and Integration


GFA Young Researchers Seminar: Efficient High-Dimensional Sampling and Integration August 30, 2017 (11:00 AM PDT - 12:30 PM PDT)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Benjamin Cousins (Georgia Institute of Technology)
Description No Description
No Video Uploaded

The search for efficient algorithms for high-dimensional sampling and integration has led to a number of deep connections to convex geometry. Notably, the KLS conjecture, a purely geometric statement about isotropic convex bodies, was made by Kannan, Lovász, and Simonovits in 1995 alongside their search for a faster volume algorithm. In this talk, I will give an overview of the algorithmic approaches used for sampling, integration, and volume computation, while illustrating the geometric and probabilistic tools used to prove the algorithmic efficiency. Additionally, I will discuss recent progress on this line of work and show an O^*(n^3) volume algorithm for well-rounded convex bodies, which was previously suspected to rely on a positive resolution of the KLS conjecture. The theoretical ideas for the algorithms also appear to transfer over to practice, and I will demonstrate a MATLAB implementation that can experimentally sample or integrate over a polytope in a few hundred dimensions. To conclude the talk, I will give a fairly in-depth discussion of interesting open questions.

No Notes/Supplements Uploaded No Video Files Uploaded