2026-07-21T14:19:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3015 2024-03-06T10:33:44Z ddc:004 open_access

The Complexity of Weighted Boolean #CSP Modulo k Guo, Heng Huang, Sangxia Lu, Pinyan Xia, Mingji #CSP dichotomy theorem counting problems computational complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Heng Guo and Sangxia Huang and Pinyan Lu and Mingji Xia 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.249 urn:nbn:de:0030-drops-30158 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.249 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode