Seminar

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.