6.S891: Algorithmic Counting and Sampling

This course introduces the modern theory of algorithms for sampling from high-dimensional probability distributions and estimating their partition functions. These fundamental algorithmic primitives lie at the foundation of statistics, physics, and machine learning. We will study a diverse set of algorithmic paradigms for solving these problems based on Markov chains, decay of correlations, geometry of polynomials, and more. We will further study the rich set of analytic, probabilistic, and algebraic tools used to give performance guarantees to these algorithms.

Administrative Stuff

Prereqs: Mathematical maturity + undergraduate understanding of discrete math, linear algebra, and algorithms/complexity
When: Tuesdays & Thursdays, 9:30am—11:00am
Where: 34-301
Office Hours: By appointment
Evaluation: 3 problem sets (each ~20% of grade) + research-based final project (~40%)
Discussion Board: Piazza
Feedback Form: Please leave anonymous constructive feedback on the course here. Or you can email me. I would greatly appreciate it!
Other Linkage: Canvas, psetpartners, (Very Approximate) Syllabus

Additional Resources

Course by Eric Vigoda
Course by Shayan Oveis Gharan
Course by Costis Daskalakis
Course by Alistair Sinclair
Course by Nima Anari
“Markov Chains and Mixing Times” by Levin—Peres—Wilmer
“Mathematical Aspects of Mixing Times” by Montenegro—Tetali
“Counting and Markov Chains” by Jerrum
“Combinatorics and Complexity of Partition Functions” by Barvinok (see also his book)
“Statistical Mechanics of Lattice Systems” by Friedli—Velenik
“Five lectures on statistical mechanics methods in combinatorics” by Will Perkins
Summer School on “Spectral Independence and Entropy Decay”

Homework

Final Project
Problem Set 1 (Due: Sept. 28, 11:59pm EST)
Problem Set 2 (Due: Nov. 2, 11:59pm EST)
Problem Set 3 (Due: Nov. 30, 11:59pm EST)
(All solutions are available on Canvas.)

Lecture Notes

Sept. 7: Intro to Counting and Sampling
Sept. 12: Markov Chain Fundamentals
Sept. 14: The Coupling Method
Sept. 19: Eigenvalues, Conductance, and Canonical Paths
Sept. 21: FPRAS for the Ferromagnetic Ising Model
Sept. 26: Phase Transitions and the Hardcore Model
Sept. 28: Correlation Decay Algorithm
Oct. 3: Polynomial Interpolation Method
Oct. 5: Monomer-Dimer Zero-Freeness
Oct. 10: No class, student holiday
Oct. 12: Lee—Yang Circle Theorem and Multivariate Stability
Oct. 17: Polymer Models and the Cluster Expansion
Oct. 19: Cluster Expansion (cont.), Functional Analysis for MCMC
Oct. 24: Spectral Independence
Oct. 26: No class, instructor sick
Oct. 31: Optimal Mixing of Glauber Dynamics, Entropic Independence
Nov. 2: Entropic Independence (cont.), Spectral Independence via Mixing
Nov. 7: Spectral Independence via Correlation Decay
Nov. 9: Spectral Independence via Zero-Freeness
Nov. 14: Matroids, Trickle-Down, and Log-Concave Polynomials
Nov. 16: Disagreement Percolation
Nov. 21: Sampling Lovász Local Lemma
Nov. 23: No class, Thanksgiving holiday
Nov. 28: Localization Schemes (Note: Some material in the appendix is still under construction.)
Nov. 30: Intro to Variational Methods, Naïve Mean-Field
Dec. 5: Convex Relaxations, Log-Concavity
Dec. 7: Gurvits Capacity, Mixed Volumes
Dec. 12: Nonlinear Large Deviations