Sampling Matchings

Complexity of Counting

Approximation in Counting and Sampling

DNF Counting

Reductions Between Sampling and Counting

Matrix-Tree Theorem

Planar Perfect Matchings

Markov Chains

Fundamental Theorem of Markov Chains

Mixing Time Growth

Strong Stationary Times

Metropolis Rule

Time Reversal Rules

Designing Markov Chains

Transport Distance

Contractive Couplings

Path Coupling

Dobrushin's Influence Matrix

Hardcore Model

Ising Model

Spectral Analysis

Functional Analysis

Entropy and Variance Contraction

Relationship between Relaxation and Mixing Time

Fourier Analysis

Continuous Time

Dirichlet Form

Comparison Method

Canonical Paths

Trading Time for Approximation

Monomer-Dimer Systems

Bipartite Perfect Matchings

Correlation Decay

Deterministic Counting

Matching Polynomial

Roots of Polynomials

Barvinok's Method

Bounded-Degree Counting Tricks

Log-Concavity of Sequences

Determinantal Distributions

High-Dimensional Expanders

Local-to-Global for f-Divergences

Log-Concavity

HDX from Half-Plane Stability

HDX from Stability

Entropic Independence

Entropy Factorization

HDX from Correlation Decay

HDX from Dobrushin

Trickle Down

Coupling from the Past

Stochastic Localization

CS 263 Counting and Sampling Stanford University Autumn 2022 The course addresses both classic and recent developments in counting and sampling. It covers counting complexity, exact counting via determinants, sampling via Markov chains, and high-dimensional expanders. 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   

CS 263 Counting and Sampling

Theoretical Computer Science

Sampling Matchings

1 courses cover this concept

CS 263 Counting and Sampling