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