18.409 Convex Geometry and Random Walks.

Tentative Schedule.

1. Introduction.

2. The Brunn-Minkowski inequality.

3,4. Optimization, finding the centroid.

5. Sampling by a random walk.

6. Markov chains, conductance and mixing time.

7,8. Isoperimetric inequalities and mixing of the ball walk.

9, 10. Logconcave functions: Inequalities.

11, 13. An n^5 volume algorithm.

Thu, Apr 1. One step of hit-and-run.

Tue, Apr 6. Hit-and-run mixes from a warm start.

Thu, Apr 8. A weighted isoperimetric inequality. Mixing from any start.

Mon, Apr 12. How to compute the volume? NOTE: 4-5pm in 2-105.

Tue, Apr 13. Divine intervention.

Thu, Apr 15. The localization lemma (Luis).

Thu, Apr 22. Average conductance (Joungkeun).

Tue, Apr 27. Logconcave functions: geometry (Alexandre).

Thu, Apr 29. Logconcave functions: sampling.

May 4,6. Hit-and-run for logconcave sampling (David+Dan).

May 11, 13. Open problems, Project presentations.