93 citations · 296 across the 10 of their papers we have counts for
5 papers · 1 filter
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
We consider Metropolis Glauber dynamics for sampling proper -colourings of the -vertex complete -ary tree when . We give both upper and lower bounds…
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…
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…
Inapproximability of the Tutte polynomial
Leslie Ann Goldberg, Mark Jerrum
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for…