Link Search Menu Expand Document
CS 263

Counting and Sampling

Stanford University, Autumn 2023

Instructor: Nima Anari

Time: Mon, Wed 3:00 pm - 4:20 pm

Location: Hewlett 102

Recording: Lectures will be recorded and made available on Canvas. Edited recordings might be made public (beyond the class participants) at a later time.

Grading: Homework (four problem sets, each worth 20%) and final report (20%).

Prerequisites: Strong foundation in probability and linear algebra. Basic familiarity with design and analysis of algorithms.

Staff Contact: Preferably use Ed. If not possible, you can email the staff at cs263-aut2324-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
  • Reductions between counting and sampling
  • Exact counting gems: spanning trees, planar perfect matchings, etc.
  • 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

We will also try to cover some modern developments from the following topics:

  • Analysis of Markov chains via high-dimensional expanders
  • Stochastic localization and localization schemes
  • Exact sampling of infinite spin systems