The Classification Program for Counting Problems II
summary
Presents a concrete classification: symmetric Boolean constraint functions are either transformable into matchgate signatures and solved via Pfaffian perfect‑matching algorithms, or fall into algebraic families like Fibonacci gates or product/affine types and are polynomial, otherwise #P‑hard. Uses explicit holographic transformation matrices, gadget sequences and Vandermonde interpolation to reduce Tutte‑like evaluations (e.g. hardness at (3,3)) to Eulerian/Orientations on medial graphs, and proves the matchgate identities characterize exactly the realizable signatures.
AI-written summary · about
chapters (10)
- 0:00Match gates and framework
- 4:09Holland problem examples
- 8:19Holographic reductions
- 14:04Transformations in practice
- 21:30Classification overview
- 24:07Fibonacci and tractability
- 30:36Defining problem types
- 36:07Dichotomy theorems
- 42:37Match gate identities
- 50:59Techniques and future work
related talks
01h 22mTutorial 5: The GCT Chasm II
01h 25mInapproximability of Constraint Satisfaction Problems IV
23mExtending Symmetric Circuits
01h 17mInapproximability of Constraint Satisfaction Problems III
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
32mA Finite Alternation Result for Reversible Boolean Circuits
01h 17mInapproximability of Constraint Satisfaction Problems V