Nima Anari (
Course Assistant
June Vuong (
Mondays and Wednesdays 4:00pm-5:00pm
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.

Coauthor (for open problem discussions and any discussion beyond administrative/clarification questions)
Gradescope (for submitting homework solutions and the final report)


60% homework + 40% final report

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.


We will have one problem set roughly every 2-3 weeks.


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]


I will gradually provide links for further reading here.