Abstract / Description of output
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 language | English |
---|---|
Title of host publication | 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 249-260 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-939897-25-5 |
DOIs | |
Publication status | Published - 2011 |
Event | STACS 2011 - Dortmund, Germany Duration: 10 Mar 2011 → 12 Mar 2011 http://drops.dagstuhl.de/portals/extern/index.php?semnr=11001 |
Conference
Conference | STACS 2011 |
---|---|
Country/Territory | Germany |
City | Dortmund |
Period | 10/03/11 → 12/03/11 |
Internet address |