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

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.