The Complexity of Weighted Boolean CSP Modulo k

Heng Guo, Sangxia Huang, Pinyan Lu, Mingji Xia

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publication28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages249-260
Number of pages12
ISBN (Electronic)978-3-939897-25-5
DOIs
Publication statusPublished - 2011
EventSTACS 2011 - Dortmund, Germany
Duration: 10 Mar 201112 Mar 2011
http://drops.dagstuhl.de/portals/extern/index.php?semnr=11001

Conference

ConferenceSTACS 2011
CountryGermany
CityDortmund
Period10/03/1112/03/11
Internet address

Fingerprint Dive into the research topics of 'The Complexity of Weighted Boolean CSP Modulo k'. Together they form a unique fingerprint.

Cite this