Counting Complexity and Phase Transitions Boot Camp
as the organisers put it
Research on computational aspects of counting problems and partition functions has recently seen significant advances. This program aims to better understand the computational complexity of both exact and approximate counting problems, and their relationship to phase transitions in combinatorics and statistical physics.
who it's for
complexity theorists, algorithm designers, statistical physicists, probabilists and random processes researchers, combinatorics researchers, graduate students in theoretical CS
topics
Pfaffian orientations and Kasteleyn/FKT algorithm; matchgates and holographic reductions; Markov chain mixing times and coupling; conductance and canonical paths; Metropolis filter and MCMC sampling; coupling from the past exact sampling; partition function and free energy per particle; decay of correlations in spin systems; random K-SAT thresholds and survey propagation; dichotomy theorems for counting CSPs; approximate counting, FPRAS and BIS reductions; polymorphisms, gadget constructions and Fourier matrix decompositions
| title | author | length |
|---|---|---|
| The Classification Program for Counting Problems I | Jin-Yi Cai | 01h 00m |
Covers the concrete claim that perfect matchings on planar graphs are computable in polynomial time by reducing the count to a Pfaffian via a Kasteleyn/FKT… | ||
| Approximate Counting I | Leslie Ann Goldberg | 01h 02m |
Survey claims three coarse approximation classes: problems with an FPRAS, NP‑hard ones (SAT‑level), and an intermediate class centered on BIS (counting… | ||
| Markov Chain Mixing Times and Applications I | Ivona Bezáková, Nayantara Bhatnagar | 01h 02m |
Starts from Markov chains, defines ergodic chains and mixing time, links convergence to the spectral gap (eigenvalue 1 vs second eigenvalue) and shows how to… | ||
| Where the Hard Things Are | Andrea Montanari | 01h 07m |
Random K-SAT exhibits a sharp satisfiability threshold ~4.267 for k=3 and a geometry where solutions break into exponentially many well-separated clusters then… | ||
| Markov Chain Mixing Times and Applications II | Nayantara Bhatnagar | 01h 02m |
Metropolis chain on proper colorings mixes in order O(n log n) when the number of colors satisfies q > 4Δ via a simple coupling that contracts expected Hamming… | ||
| Dichotomy Theorems for Counting Problems I | Xi Chen | 58m |
Classifies partition functions Z_A(G) for any complex symmetric matrix A as either polynomial-time computable or #P-hard, with tractable cases exactly the… | ||
| Approximate Counting II | Davin Richerby | 56m |
Gives a trichotomy for approximately counting Boolean CSP solutions: if every relation is affine then exact counting runs in polynomial time via Gaussian… | ||
| The Partition Function, Sampling and Equilibration in Physics | Florent Krzakala, Lenka Zdeborova | 01h 11m |
Physicist framing focuses on the free energy as log Z per particle and uses Monte Carlo heuristics to locate sharp phase transitions; empirically mixing time… | ||
| Constraints, Gadgets, and Invariants | Andrei Bulatov | 54m |
Gadget constructions reduce CSPs to each other by wiring small constraint networks; polymorphisms characterize gadget reductions for decision CSPs (and for… | ||
| The Classification Program for Counting Problems II | Jin-Yi Cai | 01h 03m |
Presents a concrete classification: symmetric Boolean constraint functions are either transformable into matchgate signatures and solved via Pfaffian… | ||
| Dichotomy Theorems for Counting Problems II | Xi Chen | 58m |
Dichotomy: every counting CSP over a fixed finite language is either computable in polynomial time or #P-hard. The easy side is exactly those languages… | ||
| Markov Chain Mixing Times and Applications III | Ivona Bezáková | 58m |
Introduces conductance bounds tied to spectral gap and uses conductance and canonical paths to get explicit mixing-time estimates, then builds canonical paths… | ||
| Random Constraint Satisfaction Problems | Nike Sun | 58m |
Random k‑SAT has a sharp satisfiability threshold predicted by the physics one‑step replica symmetry breaking formula and proven for sufficiently large k; the… | ||
| The Classification Program for Counting Problems III | Heng Guo | 55m |
Classifies planar Holant problems: symmetric complex-weighted signatures are either in one of the tractable families (affine, product, matchgate after… | ||
| Decay of Correlations in Spin Systems | Yitong Yin | 01h 03m |
Shows that the algorithmic phase transition aligns with the uniqueness threshold on the infinite (d+1)-regular tree and gives a concrete route to algorithms… | ||
| The Simple, Little and Slow Things Count: On Parameterized Counting Complexity | Radu-Cristian Curticapean | 01h 08m |
Shows concrete limits: uses the Holant framework with nonplanar matchgates and a new combined signatures trick to reduce #3SAT and parameterized #CSPs to… | ||
| nothing matches | ||