A Complete Dichotomy Rises from the Capture of Vanishing Signatures
| Computer Science/Discrete Mathematics Seminar I | |
| Topic: | A Complete Dichotomy Rises from the Capture of Vanishing Signatures |
| Speaker: | Jin-Yi Cai |
| Affiliation: | University of Wisconsin |
| Date: | Monday, November 19 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
Holant Problems are a broad framework to describe counting problems. The framework generalizes counting Constraint Satisfaction Problems and partition functions of Graph Homomorphisms.
We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions $\mathcal{F}$, also called signatures, on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric signatures (taking values without a finite modulus).
The dichotomy theorem has an explicit tractability criterion.
A Holant problem defined by $\mathcal{F}$ is solvable in polynomial time if it satisfies this tractability criterion, and is \#P-hard otherwise.
The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean \#CSP. Holographic transformations play an indispensable role, not only as a proof technique, but also in the statement of the dichotomy criterion.