Syllabus (subjected to changes):

1. Overview of sampling & applications. Draft notes for Lecture 1

+  Approximate sampling and approximate counting

+ Total variation distance, coupling for distributions, data processing inequality.

+ Some example algorithms/stochastic processes for sampling: the Glauber dynamics, auto-regression, masked diffusion.

2. Markov chains and mixing time: an introduction

+ Stationary distribution, ergodicity, reversibility, mixing time

+ Example: random walk on graphs

3. Spectral gap, Poincaré inequality, (modified) Log-Sobolev inequality

4. Conductance, Cheeger's inequality, and canonical paths

5. Equivalence between approximate sampling and counting

6. Stochastic localization

   • Measure decomposition

   • Connection to denoising diffusion

7. Spectral independence

8. Entropic Independence

9. Spectral & entropic independence via trickle-down

• Applications: fast mixing of Markov chains for high-temperatured Ising models

10. Spectral & entropic independence via tree-recursion

• Applications: hardcore model (weighted independent sets)

11. Spectral & entropic independence via zero-freeness

    • Applications: uniform planar matchings, uniform distribution over fixed-size independent sets

12. Computational hardness of sampling

• Applications: hardness of sampling from low-temperatured Ising models

13. Sampling from continuous domains

+ Examples: Langevin dynamics, denoising diffusion

+ Controlling discretization error via Girsanov

14. Parallelizing the Langevin dynamics with Picard iteration

15. Parallelizing denoising diffusion with the pinning lemma

16. Quantum Markov chains

...