The Classification Program for Counting Problems III
summary
Classifies planar Holant problems: symmetric complex-weighted signatures are either in one of the tractable families (affine, product, matchgate after holographic transformations, or a special orientation family) or are #P-hard. Proof uses FKT/matchgate algorithms, gadget constructions, and interpolation: builds an exponential-accuracy gadget that approximates the 1/3 identity entries to recover exact counts, compresses redundant 3×3 signature matrices, and uses eigenvalue analysis plus induction to reduce all nontractable cases to a hard core, completing the dichotomy.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 2:39Edge Coloring
- 6:08Profile Matching
- 6:39Match Gates
- 7:28Holographic Transformation
- 10:52SelfTransformation
- 16:55Practical Cases
- 17:05ffine functions
- 18:41vanishing
- 19:43symmetrization
- 20:12superposition
- 23:45Fibonacci gates
- 26:26Transformations
- 28:33Counting orientations
- 32:49Symmetric functions
- 36:48Three steps
- 38:50Approximation
- 43:08Integration
- 44:34Interpolation
- 45:19Stratification
related talks
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 22mTutorial 5: The GCT Chasm II
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
01h 00mAverage-case Complexity for Polynomials, and All That
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 17mInapproximability of Constraint Satisfaction Problems III
56mEntropy, Capacity, and Counting
30mThe Hitting Proof System