93 citations · 296 across the 10 of their papers we have counts for
Showing 2007 · cs.CCShow all
2 papers · 2 filters
cs.CC2007★ 2 cited
An approximation trichotomy for Boolean #CSP
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a const…
cs.CC2007★ 63 cited
The Complexity of Weighted Boolean #CSP
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is par…