95 citations · 675 across the 48 of their papers we have counts for
53 papers
Approximate counting of vertices of 0/1 polytopes: a stronger hardness result
Heng Guo, Mark Jerrum
We show that approximately counting the vertices of a bounded 0/1 polytope, presented as a system of rational linear inequalities, is, informally speaking, NP-hard. In particular,…
On the self-intersection time of non-backtracking random walks
Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed we show that the expected self-intersection time i…
The antiferromagnetic Ising model beyond line graphs
Mark Jerrum
Both the antiferromagnetic Ising model and the hard-core model could be said to be tractable on line graphs of bounded degree. For example, Glauber dynamics is rapidly mixing in bo…
Zero-free regions for the independence polynomial on restricted graph classes
Mark Jerrum, Viresh Patel
Generalising the Heilman-Lieb Theorem from statistical physics, Chudnovsky and Seymour [J. Combin. Theory Ser. B, 97(3):350--357] showed that the univariate independence polynomial…
Rapid mixing of the flip chain over non-crossing spanning trees
Konrad Anand, Weiming Feng, Graham Freifeld +3
We show that the flip chain for non-crossing spanning trees of points in convex position mixes in time . We use connections between Fuss-Catalan structures to c…
Glauber dynamics for the hard-core model on bounded-degree -free graphs
Mark Jerrum
The hard-core model has as its configurations the independent sets of some graph instance . The probability distribution on independent sets is controlled by a `fugacity' ,…