Output details
11 - Computer Science and Informatics
University of Leeds
Article title
An approximation trichotomy for Boolean #CSP
Type
D - Journal article
Title of journal
Journal of Computer and System Sciences
Article number
-
Volume number
76
Issue number
3-4
First page of article
267
ISSN of journal
0022-0000
Year of publication
2010
URL
-
Number of additional authors
2
Additional information
<10>This paper shows an approximate counting trichotomy for the Boolean constraint satisfaction problem. The three classes are polynomial time, #P-hard (the hardest counting problems), and a third class, #BIS. This surprising result gives the first, and possibly the only, complete complexity classification for approximate counting problems. The class #BIS, introduced by the authors (with Greenhill) in 2003, is central to all subsequent work in approximate counting complexity. The paper appeared in Journal of Computer and System Sciences, one of the three best theoretical computer science journals. This paper is in a stream of work cited for my 2013 EATCS award.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
13
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
