52 citations · 150 across the 20 of their papers we have counts for
3 papers · 1 filter
The complexity of weighted and unweighted #CSP
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +3
We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our red…
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
Martin Dyer, David Richerby
Bulatov (2008) gave a dichotomy for the counting constraint satisfaction problem #CSP. A problem from #CSP is characterised by a constraint language, which is a fixed, finite set o…
The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)
Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius +1
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs wi…