Approximate Counting I
summary
Survey claims three coarse approximation classes: problems with an FPRAS, NP‑hard ones (SAT‑level), and an intermediate class centered on BIS (counting independent sets in bipartite graphs). Tools are AP‑reductions, Markov chain/decay techniques (not detailed) and algebraic rewrites: Potts = homomorphisms to stretched stars, ferromagnetic Ising on hypergraphs = random‑cluster formulation so it reduces to BIS. Jerrum–Sinclair gives an FPRAS for graph Ising; many Potts/certain tree cases remain open.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:17The Complexity of Approximate Counting
- 2:25Example: The Potts model
- 12:32How difficult is it to FPRAS a problem in #P?
- 15:36Relative Complexity of Approximate Counting
- 20:17Three classes of interreducible classes within #P
- 21:57Another impossible goal
- 25:13Graph Homomorphisms
- 35:41A trichotomy for weighted homomorphisms to trees
- 41:07Approximate counting problems which are =AP #BIS
- 46:09The ferro Ising partition function of a hypergraph
- 50:12#BIS Cap Ferromagnetic Hypergraph Ising
related talks
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 17mInapproximability of Constraint Satisfaction Problems III
01h 25mInapproximability of Constraint Satisfaction Problems IV
57mTowards P≠NP from Extended Frege Lower Bounds
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
01h 01mThe Gospel According to TCS
56mEntropy, Capacity, and Counting
47mNatural Proofs in Algebraic Circuit Complexity