The Simple, Little and Slow Things Count: On Parameterized Counting Complexity
summary
Shows concrete limits: uses the Holant framework with nonplanar matchgates and a new combined signatures trick to reduce #3SAT and parameterized #CSPs to counting perfect matchings, producing graphs with only O(n) crossings or O(k) apices. Proves ETH/#ETH-style conditional lower bounds that rule out subexponential-in-parameter algorithms (e.g. no 2^{o(genus)} or n^{o(k)} time for these restricted families), and gives matching FPT or near-tight upper bounds where known.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:09Classical Counting
- 5:40Parameterized Counting
- 9:24Parameterized Counting Complexity
- 11:53W1 Hardness
- 13:18Counting Small Things
- 20:13Similarities
- 21:47Taking Sharp
- 22:31Sharpeth
- 29:04Graphs with Simple Structures
- 32:49Graph Parameters
- 39:27Proof Outline
- 44:54Magic gates
- 53:38Combined Signatures
- 57:50Combined Signature Example
related talks
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 09mInformation Theory in Computational Complexity IV
01h 17mInapproximability of Constraint Satisfaction Problems III
55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic
01h 22mTutorial 5: The GCT Chasm II
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules