5 citations · 7 across the 3 of their papers we have counts for
3 papers · 1 filter
The Complexity of Weighted Boolean #CSP with Mixed Signs
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +2
We give a complexity dichotomy for the problem of computing the partition function of a weighted Boolean constraint satisfaction problem. Such a problem is parameterized by a set o…
A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum +1
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the nu…
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…