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.
|Title of host publication||28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany|
|Publisher||Institute of Electrical and Electronics Engineers (IEEE)|
|Number of pages||12|
|Publication status||Published - 2011|
|Event||STACS 2011 - Dortmund, Germany|
Duration: 10 Mar 2011 → 12 Mar 2011
|Period||10/03/11 → 12/03/11|