Output details
11 - Computer Science and Informatics
University of Leeds
An approximation trichotomy for Boolean #CSP
<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.