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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.