Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 9
Keyword [en]
#CSP, dichotomy theorem, counting problems, computational complexity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-42721DOI: 10.4230/LIPIcs.STACS.2011.249Scopus ID: 2-s2.0-79960009639ISBN: 978-3-939897-25-5 (print)OAI: oai:DiVA.org:kth-42721DiVA: diva2:447563
Conference
STACS 2011
Funder
EU, European Research Council, 6853
Note
QC 20111013Available from: 2011-10-13 Created: 2011-10-12 Last updated: 2011-10-13Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full textScopushttp://drops.dagstuhl.de/opus/volltexte/2011/3015

Authority records BETA

Huang, Sangxia

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 98 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf