Fine-Grained Counting Complexity I

on YouTube ↗01h 02m

" summary

Shows a concrete chain: counting 3D‑matching reduces to counting k‑matchings in bipartite graphs via a tiny gadget whose counts cancel mod p, recovers exact counts with the Chinese Remainder Theorem, then to the permanent; gives Ryser’s O(d·2^d) algorithm but argues no subexponential improvement under #ETH and Radu tightens this to rule out o(d) exponent speedups. Key techniques are Ryser inclusion‑exclusion and multivariate interpolation (block size r gives r^{n/r} samples), and positive results include polynomial‑time approximation for nonnegative permanents and subexponential approximate #SAT under falsified strong ETH.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 0:2550 Shades of Fine Grained
3. 1:37Outline
4. 3:33Example: Counting Hamiltonian Cycles reduces to #SAT
5. 4:48Parsimonious reductions and the counting version of NP
6. 5:54Counting solutions is harder than finding one
7. 7:31Some examples of counting problems
8. 8:52Count Perfect Matchings in Bipartite Graphs
9. 10:38Computing the permanent
10. 15:08Permanent: Probably not parsimoniously hard
11. 15:58Polynomial-time oracle reductions fromftog
12. 26:16Counting Satisfying Assignments of CNFS
13. 27:12Counting Exponential Time Hypotheses
14. 28:38Fine-Grained Complexity of the Permanent
15. 30:27Counting Solutions to 2-CNF formulas
16. 32:41Count Perfect Matchings in General Graphs
17. 33:56Chromatic polynomial & Deletion-Contraction
18. 38:47Computing the Tutte polynomial
19. 43:25Polynomial Interpolation
20. 44:07Interpolation in Counting Complexity [seriously, like, every paper in the area]
21. 49:16Block interpolation [Curticapean 15]
22. 56:32Dichotomy theorems Constraint Satisfaction Problems (CSP)

" related talks

• 28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph StreamsSoheil Behnezhad · Managing Memory 2025
• 55mSiegel's Theorem, Edge Coloring, and a Holant DichotomyJin-Yi Cai · Tensors in Computer Science and Geometry 2014
• 41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)Talya Eden · Workshop on Local Algorithms (WoLA) 2024
• 01h 00mCorrespondence Colouring of Random GraphsLiana Yepremyan, Zdenek Dvorak · Structural Results 2023
• 23mWorst-Case to Expander-Case Reductionsamir Abboud, Nathan Wallheimer · ITCS 2023
• 19mA Formal Disproof of Hirsch ConjecturePierre-Yves Strub, Xavier Allamigeon, Quentin Canu · CPP 2023
• 34mTesting Intersectingness of Uniform Families or how Dana and I intersectedMichal Parnas · Workshop on Local Algorithms (WoLA) 2024
• 25mAn Improved Lower Bound for Matroid Intersection Prophet inequalitiesS. Matthew Weinberg, Raghuvansh R. Saxena, Santhoshini Velusamy · ITCS 2023