Fine-Grained Complexity Classification of Counting Problems

on YouTube ↗31m

" summary

Fine-grained classification ties concrete running times to counting problems: CNF counting resists sub- (1+δ)^n algorithms under SETH/ETH, with examples like Schöning’s 4/3^n decision bound and branching at ~1.64^n for exact SAT, inclusion–exclusion gives permanent in ~2^d, and #ETH rules out subexponential permanent algorithms. Sparsity reductions use the sparsification lemma, parity reductions show counting hitting sets ≡ counting set covers mod 2, and a multivariate interpolation gadgetization yields tight conditional lower bounds and parsimonious reductions.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 0:11Fine-Grained Complexity Classification of Counting Problems
3. 1:19Motivation for fine-grained complexity
4. 3:40Available conjectures, problems, and classes
5. 5:143-CNF-SAT faster than exhaustive search
6. 9:19Branching algorithms
7. 13:01Sparsification Lemma
8. 14:40General CNF-SAT
9. 16:37Problems equivalent under SETH Cygan et al. 2012
10. 20:44Computing the permanent
11. 22:30Fine-Grained Complexity of the Permanent
12. 23:49Count Perfect Matchings in General Graphs
13. 24:22Chromatic polynomial & Deletion Contraction
14. 25:10The Tutte Plane of Computational Problems
15. 26:11Polynomial Interpolation
16. 27:09Approximate Counting
17. 28:08Is Counting really harder than Decision?
18. 29:25Open problems - is computing