Fine-Grained Counting Complexity II
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Classifies subgraph counting by the pattern class: if maximum matching size is bounded the problem is polynomial, otherwise counting is #W[1]-hard; proves hardness by reducing colorful cliques to counting k‑matchings via a constructive chain of vertex explosions that produces about 3^k colored‑matching instances, then removes colors by inclusion–exclusion. Uses linear algebra, the Holant/matchgate framework and planar/two‑apex gadget realizations to get concrete lower bounds (no n^{o(k/log k)} or n^{o(ωk/log k)} algorithms under #ETH), so the construction works and yields tight parameterized hardness.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:39Classical counting
- 3:03Parameterized counting
- 7:39This talk
- 18:39Colored subgraphs
- 21:51New instances
- 25:12Vertex explosions, degree 3
- 25:58Chain of explosions
- 30:11Counting perfect matchings
- 33:19Some graph parameters
- 38:59Proofs via Holants
- 39:47Holant problems
- 43:53Matchgates
- 47:06Combined signatures
- 51:50Counting sparse grid tilings
- 57:11Open problem
related talks
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
23mWorst-Case to Expander-Case Reductions
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
01h 00mCorrespondence Colouring of Random Graphs
25mOn computing homological hitting sets
A Formal Disproof of Hirsch Conjecture
27mSuccinct Preferential Attachment Graphs