Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.249
URN: urn:nbn:de:0030-drops-30158
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3015/
Guo, Heng ; Huang, Sangxia ; Lu, Pinyan ; Xia, Mingji
The Complexity of Weighted Boolean #CSP Modulo k
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{guo_et_al:LIPIcs:2011:3015,
author = {Heng Guo and Sangxia Huang and Pinyan Lu and Mingji Xia},
title = {{The Complexity of Weighted Boolean #CSP Modulo k}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {249--260},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3015},
URN = {urn:nbn:de:0030-drops-30158},
doi = {10.4230/LIPIcs.STACS.2011.249},
annote = {Keywords: #CSP, dichotomy theorem, counting problems, computational complexity}
}
| Keywords: | #CSP, dichotomy theorem, counting problems, computational complexity | |
| Seminar: | 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) | |
| Issue date: | 2011 | |
| Date of publication: | 11.03.2011 |
