The complexity of complex weighted Boolean #CSP

• Define and analyze two families of constraint functions: the product type and the affine type.
• Prove that for Boolean #CSP problems these families define polynomial time computable problems, and everything else is #P-hard.
• Extend this complexity dichotomy to Read-At-Most-Thrice Boolean #CSP.
• Introduce local holographic transformations.

We prove a complexity dichotomy theorem for the most general form of Boolean #CSP where every constraint function takes values in the field of complex numbers CC. We first give a non-trivial tractable class of Boolean #CSP which was inspired by holographic reductions. The tractability crucially depends on algebraic cancelations which are absent for non-negative numbers. We then completely characterize all the tractable Boolean #CSP with complex-valued constraints and show that we have found all the tractable ones, and every remaining problem is #P-hard. We also improve our result by proving the same dichotomy theorem holds for Boolean #CSP with maximum degree 3 (every variable appears at most three times). The concept of Congruity and Semi-congruity provides a key insight and plays a decisive role in both the tractability and hardness proofs. We also introduce local holographic reductions as a technique in hardness proofs.