Mon, Sep 26

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

Wed, Sep 28

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

Release Homework 1

Mon, Oct 3

Lecture 3: Planar Perfect Matchings; Intro to Markov Chains

Wed, Oct 5

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

Mon, Oct 10

Lecture 5: Designing Markov Chains; Transport Distance; Contractive Couplings; Intro to Path Coupling (remote on Zoom)

Wed, Oct 12

Lecture 6: Dobrushin's Influence Matrix; Hardcore and Ising Models; Intro to Spectral Analysis (remote on Zoom)

DueHomework 1

Release Homework 2

Mon, Oct 17

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

Wed, Oct 19

Lecture 8: Continuous Time; Dirichlet Form; Comparison Method

Mon, Oct 24

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

Wed, Oct 26

Lecture 10: Monomer-Dimer Systems; Bipartite Perfect Matchings

DueHomework 2

Release Homework 3

Mon, Oct 31

Lecture 11: Correlation Decay and Deterministic Counting

Wed, Nov 2

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

Mon, Nov 7

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

Wed, Nov 9

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

DueHomework 3

Release Homework 4

Mon, Nov 14

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

Wed, Nov 16

Lecture 16: HDX from Stability; Entropic Independence

Mon, Nov 28

Lecture 17: Entropic Independence; Entropy Factorization (prerecorded, no in-person class)

Wed, Nov 30

Lecture 18: HDX from Correlation Decay; HDX from Dobrushin (prerecorded, no in-person class)

DueHomework 4

Mon, Dec 5

Lecture 19: Trickle Down; Coupling from the Past

Wed, Dec 7

Lecture 20: Stochastic Localization

Report