Approximate Counting II
summary
Gives a trichotomy for approximately counting Boolean CSP solutions: if every relation is affine then exact counting runs in polynomial time via Gaussian elimination; if every relation is a conjunction of pins and implications then the problem is AP-equivalent to counting bipartite independent sets (BIS) via gadget constructions; otherwise the problem is AP-hard as #SAT. Extends to weighted, conservative languages using clone theory and log-supermodular (LSM) criteria: non-LSM functions yield #SAT-level hardness, while weak LSM reduces to LSM-on-2-element-subdomains.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:53Approximate counting (revision)
- 3:26Constraint Satisfaction Problems
- 5:36#3-SAT is a counting CSP
- 8:22CSP - alternative view
- 13:19Approximation trichotomy for Boolean #CSPC
- 32:53Example - Ising model
- 35:33Functional clones
- 39:30Log-supermodular functions
- 47:09Extending the domain
related talks
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 17mInapproximability of Constraint Satisfaction Problems III
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
56mEntropy, Capacity, and Counting
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
01h 17mInapproximability of Constraint Satisfaction Problems V