63 citations · 270 across the 27 of their papers we have counts for
3 papers · 1 filter
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…
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…
Matrix norms and rapid mixing for spin systems
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
We give a systematic development of the application of matrix norms to rapid mixing in spin systems. We show that rapid mixing of both random update Glauber dynamics and systematic…