Link Search Menu Expand Document

Counting and Sampling

Stanford University, Autumn 2022

Instructor: Nima Anari

Time: Mon, Wed 1:30 pm - 2:50 pm

Location: Gates 100

Grading: Homework (four problem sets, each worth 20%) + Final Report (20%).

Prerequisites: Strong foundation in probability and basics of design and analysis of algorithms.

Staff Contact: Preferably use Ed. If not possible, you can email the staff at cs263-aut2223-staff@lists.stanford.edu.

Topics

We will cover classic topics as well as some recent developments in counting and sampling.

Classic topics include:

  • Counting complexity and #P
  • Self-reducibility, reductions between counting and sampling
  • Exact counting via determinants: spanning trees, planar perfect matchings
  • Sampling via Markov chains
  • Probabilistic analysis of Markov chains: stationary times, path coupling, coupling from the past
  • Functional analysis of Markov chains: spectral gap, Poincare and log-Sobolev inequalities, conductance, canonical flows
  • Deterministic counting: correlation decay, zeros of polynomials, Barvinok‚Äôs method, variational methods

Recent devlopments, focusing on an emerging high-dimensional-expanders-based lens, include:

  • Trickle down and and the local-to-global method
  • Matroids and log-concave polynomials
  • Spectral independence, entropic independence, entropy factorization
  • Establishing high-dimensional expansion from coupling, correlation decay, zero-freeness
  • Stochastic localization

Frequently Asked Questions

  • Will the lectures be recorded? No, not officially. Unofficially, we will try our best to record in-class videos and make them available on Canvas, but we can provide no guarantees; if the recording quality does not end up OK, or if recording ends up being disruptive to the instruction, we will stop recording.
  • Is the course remote-friendly? No. See the above answer. We will not track attendance and homeworks and the final report can be turned in online, but we cannot guarantee you will be able to watch the lectures remotely.