Change search
ReferencesLink to record
Permanent link

Direct link
The Complexity of Weighted Boolean #CSP Modulo k
University of Wisconsin - Madison. (Computer Sciences Department)
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1600-5290
Microsoft Research Asia. (Theory Group)
2011 (English)In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 / [ed] Thomas Schwentick and Christoph Dürr, Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 2011, 249-260 p.Conference paper (Refereed)
Abstract [en]

We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k  for any positive integer k1 . 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 .

Place, publisher, year, edition, pages
Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 2011. 249-260 p.
, Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 9
Keyword [en]
#CSP, dichotomy theorem, counting problems, computational complexity
National Category
Computer Science
URN: urn:nbn:se:kth:diva-42721DOI: 10.4230/LIPIcs.STACS.2011.249ScopusID: 2-s2.0-79960009639ISBN: 978-3-939897-25-5OAI: diva2:447563
STACS 2011
EU, European Research Council, 6853
QC 20111013Available from: 2011-10-13 Created: 2011-10-12 Last updated: 2011-10-13Bibliographically approved

Open Access in DiVA

fulltext(696 kB)68 downloads
File information
File name FULLTEXT01.pdfFile size 696 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Huang, Sangxia
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 68 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 75 hits
ReferencesLink to record
Permanent link

Direct link