STOC 2015 Tutorial:
Sampling and Volume Computation in High Dimension

Santosh S. Vempala

High-dimensional sampling has applications in many fields, and efficient algorithms for sampling and integration have become part of the standard algorithmic toolkit. The past three decades have witnessed remarkable improvements in the worst-case complexity of these problems and resulted in a rich set of algorithmic and analytic tools. This tutorial will be an in-depth exposition of the state-of-the-art in sampling algorithms, their applications, and relevant developments in asymptotic convex geometry. Only a basic knowledge of linear algebra, probability and algorithms will be assumed. The tutorial will conclude with a discussion of open problems and research directions on all three major aspects: algorithms, probability/Markov chains and geometry.

Slides from the tutorial: Part I, Part II

Here is an outline of topics covered:

1. Introduction Model, problems, structure of high-dimensional convexity
2. Algorithms Integration, optimization, learning via sampling; simulated annealing
Demo/exercise Experiments with a MATLAB implementation
3. Asymptotic Convex Geometry Concentration; Isoperimetry; KLS, thin-shell and slicing conjectures
4. Probability Geometric Markov chains, conductance.