On the Power of Holographic Algorithms with Matchgates
summary
Classifies every Boolean complex-weighted counting CSP into exactly three cases: polynomial-time for all graphs, #P-hard on general graphs but polynomial-time on planar graphs, or #P-hard even on planar graphs. Proves the planar-easy class is precisely those holographic reductions to matchgates (i.e. FKT-type computations), using parity constraints, arity reduction to unary failures, symmetric dichotomy, and construction of crossover/equality gadgets. Main tools are complex-valued tensor algebra, planar perfect-matching technology and combinatorial reductions.
AI-written summary · about
chapters (21)
- 0:00Introduction
- 0:50Graph Homomorphism
- 1:40Partition Functions
- 6:25Counting CSP
- 8:45Constraint Functions
- 11:10Function Classes
- 14:35Do Nothing
- 15:35Signature Grid
- 16:55FKTi
- 18:00Les
- 21:05Incidence Graph
- 22:25Holographic Transformation
- 25:20Magic 8 signatures
- 26:25Theorem
- 28:10Matchgates
- 29:05Polynomials
- 32:00Ultimate Transformation
- 33:30Fourier Transformation
- 34:30Parity
- 39:45Equality
- 40:40CSP