# The Complexity of Weighted Boolean #CSP Modulo k

## The Complexity of Weighted Boolean #CSP Modulo k

The Complexity of Weighted Boolean #CSP Modulo k

Heng Guo, Sangxia Huang, Pinyan Lu, Mingji Xia

We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo *k* for any positive integer *k>1*. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where *k* is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer *k*.