Course Information
Time: Mon & Wed, 9:30am – 10:45am
Location: J. Erskine Love Manufacturing 185
Instructor: Zongchen Chen, chenzongchen@gatech.edu
Office hour: Thu 4:30pm – 5:30pm, KACB 2134
TA: Aditya Lonkar, alonkar9@gatech.edu
Office hour: Tue 10:30am – 11:30am, in the area between KACB 2124 & 2116
Topics
We study problems of generating random elements from a huge combinatorial set (sampling) and estimating the size of the set (counting), such as sampling spanning trees, independent sets, or proper colorings of a given graph or count their numbers. We mostly focus on Markov Chain Monte Carlo (MCMC) methods, which are simple and popular algorithms for such tasks. We discuss mathematical tools for analyzing the convergence rate of Markov chains, as well as recent developments in obtaining optimal mixing times. This is a theoretical course for graduate students with a background in combinatorics, probability theory, and analysis of algorithms.
Grading
Participation: 20%
Problem sets: 40%
Final project: 40%
More details can be found here
Lecture Notes
The lecture notes will be updated weekly.
Tentative Schedule
Aug 19, Aug 21: Counting and sampling basics, #P, self-reducibility
Aug 26, Aug 28: Markov chain basics
Sep 2: Labor Day
Sep 4, Sep 9: Coupling method, colorings, Dobrushin’s condition
Sep 11, Sep 16, Sep 18: Canonical paths, conductance, variance, Poincare inequality
Sep 23, Sep 25, Sep 30: Bases of matroids, local-to-global induction, trickle-down theorem
Oct 2, Oct 7, Oct 9: Spectral independence, optimal relaxation time, universality, disagreement percolation
Oct 14: Fall Break
Oct 16, Oct 21, Oct 23: Self-avoiding walks, Weitz’s algorithm
Oct 28, Oct 30: Stability of partition function, Barvinok’s algorithm
Nov 4, Nov 6: Entropy, entropic independence
Nov 11, Nov 13: Optimal mixing, modified log-Sobolev inequality
Nov 18, Nov 20: Field dynamics, mixing at uniqueness
Nov 25, Dec 2: Stochastic localization, proximal sampler, Ising model with spectral condition
Nov 27: Thanksgiving
Resources
Markov Chains and Mixing Times, Second Edition, David A. Levin and Yuval Peres
Counting, Sampling and Integrating: Algorithms and Complexity, Mark Jerrum
Kuikui Liu’s Course
Frederic Koehler’s Course
Nima Anari’s Course
Eric Vigoda’s Course
Daniel Štefankovič’s Course
Shayan Oveis Gharan’s Course
Summer School on Spectral Independence and Entropy Decay
Lecture Notes on Spectral Independence, Daniel Štefankovič and Eric Vigoda
Lecture Notes on Entropy and Markov Chains, Pietro Caputo
Notes on Sampling, Diffusions, and Stochastic Localization, Andrea Montanari