Publications (35)
The Parameterised Complexity of Counting Connected Subgraphs and Graph Motifs
Mark Jerrum, Kitty Meeks
Approximately Counting H-Colourings is #BIS-Hard
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
The complexity of weighted and unweighted #CSP
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg +3
The expressibility of functions on the Boolean domain, with applications to Counting CSPs
Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg +2
A complexity dichotomy for hypergraph partition functions
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
A Counterexample to rapid mixing of the Ge-Stefankovic Process
Leslie Ann Goldberg, Mark Jerrum
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg +4
The Complexity of Computing the Sign of the Tutte Polynomial
Leslie Ann Goldberg, Mark Jerrum
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
Some hard families of parameterised counting problems
Mark Jerrum, Kitty Meeks
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
Leslie Ann Goldberg, Mark Jerrum
A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum +1
Inapproximability of the Tutte polynomial
Leslie Ann Goldberg, Mark Jerrum
An approximation trichotomy for Boolean #CSP
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
The complexity of approximating conservative counting CSPs
Xi Chen, Martin Dyer, Leslie Ann Goldberg +4
The Complexity of Approximately Counting Tree Homomorphisms
Leslie Ann Goldberg, Mark Jerrum
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
Leslie Ann Goldberg, Mark Jerrum
Approximating the partition function of the ferromagnetic Potts model
Leslie Ann Goldberg, Mark Jerrum
The parameterised complexity of counting even and odd induced subgraphs
Mark Jerrum, Kitty Meeks
On the approximation of one Markov chain by another
Mark Jerrum
The complexity of parity graph homomorphism: an initial investigation
John Faben, Mark Jerrum
Inapproximability of the Tutte polynomial of a planar graph
Leslie Ann Goldberg, Mark Jerrum
Systematic scan for sampling colorings
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
Functional Clones and Expressibility of Partition Functions
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum +2
The Complexity of Weighted Boolean #CSP
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
Two remarks concerning balanced matroids
Mark Jerrum
On the switch Markov chain for perfect matchings
Martin Dyer, Mark Jerrum, Haiko Müller
Matrix norms and rapid mixing for spin systems
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum
Uniform Sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum, Jingcheng Liu
A complexity trichotomy for approximately counting list H-colourings
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
Mark Jerrum, Jung-Bae Son, Prasad Tetali +1
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Leslie Ann Goldberg, Mark Jerrum
Random cluster dynamics for the Ising model is rapidly mixing
Heng Guo, Mark Jerrum
Approximating the partition function of planar two-state spin systems
Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
Markov chain comparison
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum +1