Information

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)
Gradescope (for submitting homework solutions and the final report)

Grading

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.

Homework

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

Topics

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.

Schedule

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]

Resources

I will gradually provide links for further reading here.