The Classification Program for Counting Problems I
summary
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 algorithm. Gives the construction of a Pfaffian orientation, a sign-counting lemma tying XOR of two matchings to oriented cycles, and a proof sketch that all matching terms share a sign. Introduces matchgates as planar gadgets that yield tensors for holographic reductions and situates these tools inside the Boolean dichotomy program.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:10Frameworks
- 13:45Formal definition
- 17:16Onetoone correspondence
- 19:01Crossovers
- 22:43Polynomial Time
- 23:13Antisymmetric Edges
- 24:18Perfect Matching
- 25:02Orientation
- 29:29Two Perfect Matches
- 39:55Fafi Orientation
- 49:38Connector Graph
- 53:20Match Gates
- 55:57Holland Problem
related talks
49mPerfection and Beyond
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
01h 22mTutorial 5: The GCT Chasm II
01h 17mInapproximability of Constraint Satisfaction Problems III
18mOn the Verification of a Subgraph Construction Algorithm
53mA Commentary on the Collision of Worlds
01h 09mInformation Theory in Computational Complexity IV
56mEntropy, Capacity, and Counting