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
19mA Formal Disproof of Hirsch Conjecture
27mSuccinct Preferential Attachment Graphs