In this course we will study several techniques developed in the last 30 years to sample from sophisticated probability distributions of exponential size. Approximately half of the course will focus on classical techniques and the second half will study more recent developments.
Administrative Information
- Instructor: Shayan Oveis Gharan
- Office Hours: By appointment, email me at shayan at cs dot washington dot edu.
Ziyun's OH: Thursdays 14:30-15:30 at Gates 152 - Lectures: Monday - Wednesday 1:30 - 2:50 at CSE2 (Gates Building) 271
Assignments
Related Courses
- Kuikui Liu's Course
- Nima Anari's Course
- Eric Vigoda's Course
- Costis Daskalakis Course
- Alistair Sinclair's Course
Related Books/Monographs
- Persi Diaconis's Monograph on the mathematics of mixing things up
- Persi's Monograph on The Markov Chain Monte Carlo Revolution
- Markov Chains and Mixing Times by David Levin, Yuval Peres, and Elizabeth Wilmer. Also, take a look at the 2nd edition
- Combinatorics and Complexity of Partition Functions by Sasha Barvinok
- Algebraic Combinatorics by Chris Godsil
| Lecture | Topic | Notes | Bonus Materials | |
|---|---|---|---|---|
| Lecture 1 (09/25/24) | Equivalence of Counting and Sampling | |||
| Lecture 2 (09/30/24) | Markov chains Intro, Metropolis Rule, Glauber Dynamics and Fundamental Theorem of Markov chains | |||
| Lecture 3 (10/02/24) | Introduction to Coupling | |||
| (10/07/24) No Lecture: Instructor is traveling | ||||
| Lecture 4 (10/09/24) | Graph Coloring | |||
| Lecture 5 (10/14/24) | Functional Analysis of Markov Chains | |||
| Lecture 6 (10/16/24) | Canonical Path method and applications | |||
| Lecture 7 (10/21/24) | Sampling from the Ising Model | |||
| Lecture 8 (10/23/24) | Lower Bounds on Mixing Time | |||
| Lecture 9 (10/28/24) | Spectral Independence | |||
| Lecture 10 (10/30/24) | Spectral Independence Continued | |||
| Lecture 11 (11/04/24) | Correlation decay and Sampling from the Hardcore Model | |||
| Lecture 12 (11/06/24) | Entropic Independence and Near Linear time algorithm for the Hardcore Model | |||
| (11/11/24) No Lecture: Veternas Day | ||||
| Lecture 13 (11/13/24) | Trickledown Theorems | |||
| Lecture 14 (11/18/24) | Intro to Real Stable Polyns | |||
| Lecture 15 (11/20/24) | Matroids and Log Concave Polynomials | |||
| Lecture 16 (11/25/24) | Stochastic Localization schemes | |||
| (11/27/24) No Lecture: Thanksgiving day | ||||
| Lecture 17 (12/03/24) | Cluster Expansion | |||
| Lecture 18 (12/05/24) | ||||
