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)
Piazza (for 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. 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]

Homework

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.

Problem Set 1
Release date: 9/24/2020
Due date: 10/16/2020 at 11:00pm
[Problems] [Submit] [Solutions]
Problem Set 2
Release date: 10/8/2020
Due date: 10/30/2020 at 11:00pm
[Problems] [Submit]
Problem Set 3
Release date: 10/29/2020
Due date: 11/20/2020 at 11:00pm
[Problems] [Submit]

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]
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]

Resources

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.