- Instructor
- Nima Anari (anari@cs.stanford.edu)
- Course Assistant
- June Vuong (tdvuong@stanford.edu)
- Time
- Mondays and Wednesdays 4:00pm-5:00pm
- Location
- Online using Zoom (Zoom links in Canvas)

Videos will be recorded and put on Canvas but live participation is highly encouraged. - Office Hours
- By appointment
- Tools
Coauthor (for open problem discussions and any discussion beyond administrative/clarification questions)

Piazza (for administrative/clarification questions)

Gradescope (for submitting homework solutions and the final report)- Grading
60% homework + 40% final report

The final report should either survey a topic (1-2 papers) or present your own new (but perhaps incremental) work. An appropriate length is 2-5 pages. You are free to collaborate with others (perhaps using Coauthor), but you should write the report individually.

- Final Report
- Due date: 11/20/2020 at 11:00pm

[Submit]

We will have one problem set roughly every 2-3 weeks. Please submit your homework by the due dates at 11:00pm Pacific Time on Gradescope.

We tentatively plan to cover the following topics:

- Intro to counting complexity and #P.
- Self-reducibility and equivalence of counting and sampling.
- Exact counting using determinants: spanning trees, planar perfect matchings.
- Counting DNF solutions.
- Basics of Markov chains.
- Probabilistic analysis of MCMC: stationary times, path coupling, coupling from the past.
- Functional/spectral analysis of MCMC: conductance, spectral techniques, Poincare, and log-Sobolev.
- Correlation decay, Dobrushin's condition, spin systems.
- Methods for deterministic counting: Barvinok's method, variational methods.
- Canonical paths and bipartite perfect matchings.
- Continuous distributions: sampling from convex sets and log-concave distributions.
- High-dimensional expanders.

- Monday 9/14
- Topics: Introduction; Exact and Approximate Counting and Sampling

[Whiteboard] [Video] - Wednesday 9/16
- Topics: Self-Reducibility; Equivalence of Approximate Counting and Sampling

[Whiteboard] [Video] - Monday 9/21
- Topics: Matrix-Tree Theorem; Counting Planar Graph Perfect Matchings

[Whiteboard] [Video] - Wednesday 9/23
- Topics: Estimators for Permanent; DNF Counting

[Whiteboard] [Video] - Monday 9/28
- Topics: Network Reliability; Intro to Markov Chain Analysis

[Whiteboard] [Video] - Wednesday 9/30
- Topics: Time-Reversibility; Metropolis Rule; Glauber Dynamics; Fundamental Theorem of Markov Chains

[Whiteboard] [Video] - Monday 10/05
- Topics: Mixing Time Growth; Cutoff; Coupling and Path Coupling

[Whiteboard] [Video] - Wednesday 10/07
- Topics: Perron-Frobenius; Spectrum of Markov Chains; Fourier Analysis

[Whiteboard] [Video] - Monday 10/12
- Topics: f-Divergence; Intro to Functional Analysis; Poincare Inequality

[Whiteboard] [Video] - Wednesday 10/14
- Topics: Poincare in the Non-Reversible Case; Ideal Markov Chain and Dirichlet Form; Cheeger's Inequality

[Whiteboard] [Video] - Monday 10/19
- Topics: Walks on Trees; Time-Approximation Tradeoff; Aldous-Broder's Algorithm; Markov Chain Tree Theorem

[Whiteboard] [Video] - Wednesday 10/21
- Topics: Comparison Method; Canonical Paths/Flows; Sampling Matchings

[Whiteboard] [Video] - Moday 10/26
- Topics: Monomer-Dimer Distributions; Spin Systems

[Whiteboard] [Video] - Wednesday 10/28
- Topics: Dobrushin's Conditions; Hardcore Model; Correlation Decay

[Whiteboard] [Video] - Monday 11/2
- Topics: Weitz's Algorithm for the Hardcore Model; Intro to Barvinok's Method

[Whiteboard] [Video] - Wednesday 11/4
- Topics: Barvinok's Method; Roots of the Matching Polynomial

[Whiteboard] [Video] - Monday 11/9
- Topics: Counting in Bounded-Degree Graphs; Intro to Variational Methods

[Whiteboard] [Video] - Wednesday 11/11
- Topics: Variational Methods; Mean Field; Entropy Subadditivity and Shearer's Lemma

[Whiteboard] [Video] - Monday 11/16
- Topics: Entropy Lower Bounds; Log-Concave Polynomials; High-Dimensional Expanders

[Whiteboard] [Video] - Wednesday 11/18
- Topics: High-Dimensional Expanders; Sampling from Convex Sets; Course Review

[Whiteboard] [Video]

I will gradually provide links for further reading here. Some resources are freely available electronically through Stanford library. I suggest using Lean Library to access those.

- Markov Chains and Mixing Times (by David Levin, Yuval Peres, Elizabeth Wilmer)
- Combinatorics and Complexity of Partition Functions (by Alexander Barvinok)
- Notes on Sampling and Counting (by Alan Frieze)
- Mathematical Aspects of Mixing Times in Markov Chains (by Ravi Montenegro and Prasad Tetali)
- Lecture notes on Probability and Computation (by Costis Daskalakis)
- Lecture notes on Counting and Sampling (by Shayan Oveis Gharan)
- Lecture notes on Markov Chain Monte Carlo Methods (by Eric Vigoda)
- Lecture notes on Markov Chain Monte Carlo Algorithms (by Dana Randall)
- Lecture note on Counting Complexity (by Luca Trevisan)
- Lecture notes on Probability Theory: The Coupling Method (by Frank den Hollander)