Lectures

Lecture 1: Complexity of Counting; Approximation in Counting and Sampling; DNF Counting

Lecture 2: Reductions Between Sampling and Counting; Matrix-Tree Theorem

Lecture 3: Planar Perfect Matchings; Intro to Markov Chains

Lecture 4: Fundamental Theorem of Markov Chains; Mixing Time Growth; Strong Stationary Times; Metropolis Rule and Time Reversal Rules

Lecture 5: Designing Markov Chains; Transport Distance; Contractive Couplings; Intro to Path Coupling

Lecture 6: Dobrushin's Influence Matrix; Hardcore and Ising Models; Intro to Spectral Analysis

Lecture 7: Functional Analysis; Entropy and Variance Contraction; Relationship between Relaxation and Mixing Time; Intro to Fourier Analysis

Lecture 8: Continuous Time; Dirichlet Form; Comparison Method

Lecture 9: Canonical Paths; Trading Time for Approximation; Sampling Matchings

Lecture 10: Monomer-Dimer Systems; Bipartite Perfect Matchings

Lecture 11: Correlation Decay and Deterministic Counting

Lecture 12: Matching Polynomial; Roots; Barvinok's Method

Lecture 13: Bounded-Degree Counting Tricks; Log-Concavity of Sequences; Determinantal Distributions

Lecture 14: High-Dimensional Expanders; Local-to-Global for f-Divergences

Lecture 15: Log-Concavity; HDX from Half-Plane Stability

Lecture 16: HDX from Stability; Entropic Independence

Lecture 17: Entropic Independence; Entropy Factorization

Mon, Nov 28, 1:30 pm – 2:50 pm (prerecorded, no in-person class)

Lecture 18: HDX from Correlation Decay; HDX from Dobrushin

Wed, Nov 30, 1:30 pm – 2:50 pm (prerecorded, no in-person class)

Lecture 19: Trickle Down; Coupling from the Past

Lecture 20: Stochastic Localization