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 | Sampling Matchings in General Graphs Random Cluster Dynamics for Ising Model Sampling Perfect Matchings in Bipartite Graphs | ||
| 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) | Correlation decay | Quantum Gibbs Sampling Mixing Time of Quantum MC | ||
| (11/11/24) No Lecture: Veternas Day | ||||
| Lecture 13 (11/13/24) | Entropic Independence | Spectral Indep of Hardcore Model Entropy Factorization | ||
| Lecture 14 (11/18/24) | Spectral Independence from Geometry of Polynomials | |||
| Lecture 15 (11/20/24) | Matroids and Log Concave Polynomials | |||
| Lecture 16 (11/25/24) | Max Entropy Programs and MLSI constant | |||
