Dichotomy Theorems for Counting Problems I
summary
Classifies partition functions Z_A(G) for any complex symmetric matrix A as either polynomial-time computable or #P-hard, with tractable cases exactly the block‑rank‑one and tensor products of Fourier matrices (and their rank‑one/2×2 exceptions); proves hardness by gadget reductions G^(p) and interpolation to nonnegative cases using the Bulatov‑Grohe dichotomy; isolates discrete unitary matrices and proves a group condition lemma so that either B^(p) violates Bulatov‑Grohe (hence #P‑hard) or A decomposes into known solvable tensors; algorithms use quadratic exponential‑sum evaluations and Gauss sums.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:13Dichotomy Theorem
- 1:51Schaeffers dichotomy theorem
- 2:41Classical counting problems
- 3:20Study frameworks
- 5:51Counting version
- 16:25Cancellations
- 17:27Goldberg Grove German
- 19:01The Plan
- 19:56The Algorithm
- 21:39Easy to Solve
- 26:54Free Matrices
- 27:49Summary
- 28:16Proof
- 30:33General Theorem
- 32:57Group Condition
- 54:15Conclusion
- 55:00Plan for tomorrow
related talks
01h 00mMatrix Rank – Extensions, Applications and Open Problems
56mEntropy, Capacity, and Counting
01h 00mAverage-case Complexity for Polynomials, and All That
29mExtended Formulations and Information Complexity
01h 17mInapproximability of Constraint Satisfaction Problems V
30mDetermination Problems for Orbit Closures and Matrix Groups
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
01h 22mTutorial 5: The GCT Chasm II