Dichotomy Theorems for Counting Problems II
summary
Dichotomy: every counting CSP over a fixed finite language is either computable in polynomial time or #P-hard. The easy side is exactly those languages satisfying strong balance (equivalently congruence singularity), which yield a Mal'tsev‑style “much of” polymorphism and let one build polynomial‑size witness functions and a small set of representative vectors. These data structures feed a backward‑induction algorithm that evaluates the partition function. Extensions cover nonnegative weights; the complex‑valued criterion needs extra orthogonality/type conditions and its decidability remains open.
AI-written summary · about
chapters (7)
- 0:00Start
- 6:48Tractability Criterion
- 9:08The Dichotomy Theorem
- 12:03Match of Polymorphism
- 21:48Witness Functions
- 49:13The Difficulties in Building Such Data Structures
- 52:30Backwards Induction
related talks
56mEntropy, Capacity, and Counting
01h 17mInapproximability of Constraint Satisfaction Problems III
47mNatural Proofs in Algebraic Circuit Complexity
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory
01h 01mThe Gospel According to TCS
01h 17mInapproximability of Constraint Satisfaction Problems V
57mTowards P≠NP from Extended Frege Lower Bounds