Publications available online
Jump to year:
1993, 1994, 1995,
1996, 1997, 1998,
1999, 2000, 2001,
2002, 2003, 2004,
2006, 2007,
2008, 2009, 2010,
2011, 2012, 2013,
2014, 2015, 2016,
2017, 2018

Complementary partial orders and rectangle packing
Mark Jerrum
Technical Report,
University of Edinburgh, Department of Computer Science, 1985.
CSR19085

Approximating the Permanent
Mark Jerrum and Alistair Sinclair,
SIAM Journal on Computing 18 (1989), 11491178.
DOI 10.1137/0218077. Download PDF.

Polynomialtime approximation algorithms for the Ising model
Mark Jerrum and Alistair Sinclair,
SIAM Journal on Computing 22 (1993), 10871116.
DOI 10.1137/0222066. Download PDF.

Uniform sampling modulo a group of symmetries
using Markov chain simulation
Mark Jerrum
LFCS report
ECSLFCS93272

Counting trees in a graph is #Pcomplete
Mark Jerrum, Information Processing Letters 51 (1994), 111116.
DOI 10.1016/00200190(94)000859

Simple translationinvariant concepts are hard to learn
Mark Jerrum, Information and Computation 113 (1994), 300311.
DOI 10.1006/inco.1994.1074

Threedimensional statistical data security problems
Robert W. Irving and Mark R. Jerrum,
SIAM Journal on Computation 23 (1994), 170184.
DOI 10.1137/S0097539790191010

The computational complexity of counting
Mark Jerrum,
Proceedings of the International Congress of Mathematicians,
Zürich, BirkhäuserVelag, 1994.
LFCS report
ECSLFCS94296

Computational Pólya theory
Mark Jerrum, Surveys in Combinatorics, 1995,
Peter Rowlinson (ed.)
London Mathematical Society Lecture Note Series 218,
Cambridge University Press, 1995.
DOI 10.1017/CBO9780511662096.006
LFCS report ECSLFCS95317

A very simple algorithm for estimating the number of kcolourings of a lowdegree graph
Mark Jerrum, Random Structures and Algorithms 7 (1995), 157165.
DOI 10.1002/rsa.3240070205

An analysis of a Monte Carlo algorithm for estimating the permanent
Alan Frieze and Mark Jerrum, Combinatorica 15 (1995), 6783.
DOI 10.1007/BF0129446

Bounding the VapnikChervonenkis dimension of concept classes parameterized by real numbers
Paul Goldberg and Mark Jerrum, Machine Learning 18 (1995), 131148.
DOI 10.1007/BF00993408

A mildly exponential approximation algorithm for the permanent
Mark Jerrum and Umesh Vazirani,
Algorithmica 16 (1996), 392401.
DOI 10.1007/BF01940871

Generating and counting Hamilton cycles in random regular graphs
Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson and Nicholas Wormald,
Journal of Algorithms 21 (1996), 176198.
DOI 10.1006/jagm.1996.0042

A polynomialtime algorithm for deciding bisimulation equivalence
of normed Basic Parallel Processes
Yoram Hirshfeld, Mark Jerrum and Faron Moller,
Mathematical Structures in Computer Science 6 (1996), 251259.
DOI 10.1017/S0960129500000992

A polynomial algorithm for deciding bisimilarity of normed contextfree processes
Yoram Hirshfeld, Mark Jerrum, and Faron Moller,
Theoretical Computer Science (1996), 143159.
DOI 10.1016/03043975(95)00064X
A preliminary version appeared in: 35th Annual IEEE Symposium on Foundations of Computer Science, 1994.
 The Markov chain Monte Carlo method:
an approach to approximate counting and integration
Mark Jerrum and Alistair Sinclair.
In Approximation Algorithms for NPhard Problems, (Dorit Hochbaum,
ed.), PWS, 1996.
Draft version.

A quasipolynomialtime algorithm for sampling words from a contextfree language
Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk and Steve Mahaney,
Information and Computation 134 (1997), 5974.
DOI 10.1006/inco.1997.2621

Improved approximation algorithms for MAX kCUT and MAX BISECTION
Alan Frieze and Mark Jerrum,
Algorithmica 18 (1997), 6781.
DOI 10.1007/BF02523688

Doubly logarithmic communication algorithms
for opticalcommunication parallel computers
Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, and Satish Rao,
SIAM Journal on Computing 26 (1997), 11001119.
DOI 10.1137/S0097539793259483

The Metropolis algorithm for graph bisection
Mark Jerrum and Gregory B. Sorkin,
Discrete Applied Mathematics 82 (1998), 155175.
DOI 10.1016/S0166218X(97)001339

Approximately Counting Hamilton Paths and Cycles in Dense Graphs
Martin Dyer, Alan Frieze and Mark Jerrum,
SIAM Journal on Compututing 27 (1998), 12621272.
DOI 10.1137/S009753979426112X
 Mathematical foundations of the Markov chain Monte Carlo method
A draft of a chapter to appear in a volume
connected with a summer
school on Probabilistic Methods for Algorithmic Discrete
Mathematics in Montpellier, August 1998.

An Omega(sqrt(log log n)) lower bound for routing in optical
networks
Leslie Ann Goldberg, Mark Jerrum, and Philip D. MacKenzie,
SIAM Journal on Computing 27 (1998), 10831098.
DOI 10.1137/S0097539794272569
 An elementary analysis of a procedure for sampling points in a convex body
Russ Bubley, Martin Dyer and Mark Jerrum,
Random Structures and Algorithms 12 (1998), 213235.
DOI
10.1002/(SICI)10982418(199805)12:3<213::AIDRSA1>3.0.CO;2Y
 Bisimulation equivalence is decidable for normed Process Algebra
Yoram Hirshfeld and Mark Jerrum,
LFCS report ECSLFCS98386
 The SwendsenWang process does not always mix rapidly
Vivek K. Gore and Mark R. Jerrum, Journal of Statistical Physics
97 (1999), 6786.
DOI 10.1023/A:1004610900745
An extended abstract appeared in:
Proceedings of the 29th ACM Symposium on Theory of Computing, 1997.
 On Approximately counting colorings of small degree graphs
Russ Bubley, Martin Dyer, Catherine Greenhill, and Mark Jerrum,
SIAM Journal on Computing 29 (1999), 387400.
DOI 10.1137/S0097539798338175

Counting unlabelled subtrees of a tree is #Pcomplete
Leslie Ann Goldberg and Mark Jerrum,
LMS Journal of Computation and Mathematics, 3 (2000), 117124.
Abstract/Download in pdf.
 Randomly Sampling Molecules
Leslie Ann Goldberg and Mark Jerrum,
SIAM Journal on Computing 29 (2000), 834853
DOI 10.1137/S0097539797318864
A preliminary version appeared in: Proceedings of the 8th ACM/SIAM
Symposium on Discrete Algorithms (SODA), 1997.
 An extension of path coupling and its application
to the Glauber dynamics for graph colorings
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill,
Mark Jerrum and Michael Mitzenmacher,
SIAM Journal on Computing 30 (2001), 19621975.
DOI 10.1137/S0097539700372708
An extended abstract appeared in: Proceedings of the 11th ACM/SIAM
Symposium on Discrete Algorithms (SODA), 2000.
 Convergence of the Iterated Prisoner's Dilemma game
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Gabriel Istrate
and Mark Jerrum,
Combinatorics, Probability and Computing 11
(2002), 135147.
DOI 10.1017/S096354830100503X
 On counting independent sets in sparse graphs
Martin Dyer, Alan Frieze and Mark Jerrum,
SIAM Journal on Computing 31 (2002), 15271541.
DOI 10.1137/S0097539701383844
A preliminary version appeared in:
40th Annual IEEE Symposium on Foundations of Computer Science, 1999.
 Spectral gap and logSobolev constant for balanced matroids
Mark Jerrum and JungBae Son,
Proceedings of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS'02), IEEE Computer Society Press, 2002, 721729.
This material was refined and generalised, and appeared
in Annals of Applied Probability
14 (2004); see below.
 The "Burnside process" converges slowly
Leslie Ann Goldberg and Mark Jerrum,
Combinatorics, Probability and Computing 11 (2002), 2134.
DOI 10.1017/S096354830100493X
 The computational complexity of twostate spin systems
Leslie Ann Goldberg, Mark Jerrum and Mike Paterson,
Random Structures and Algorithms 23 (2003), 133154.
DOI 10.1002/rsa.10090
 Lecture Notes from a Nachdiplomvorlesung
at ETHZürich
"Counting, sampling and integrating: algorithms and complexity"
Mark Jerrum, with the assistance of several others.
 Chapter 1
(with Zsuzsanna Lipták),
Two good counting algorithms.
 Chapter 2 (with Uli Wagner)
#Pcompleteness.
 Chapter 3 (with Uli Wagner)
Sampling and counting.
 Chapter 4 (???)
Coupling and colourings.
 Chapter 5 (with Michael Hoffmann
and Bernd Gärtner)
Canonical paths and matchings.
 Chapter 6 (with Alex Below
and Christoph Ambühl)
Volume of a convex body.
 Chapter 7 (with Samuele Pedroni)
Inapproximability.
 Chapter 8
Inductive bounds, cubes, trees and matroids. Draft as at 09/09/04.
 Chapter 9
Logarithmic Sobolev inequalities. Draft as at 21/02/05.
 Bibliography.
Chapters 17 published as:
Mark Jerrum,
Counting, Sampling and Integrating: algorithms and complexity,
Lectures in Mathematics  ETH Zürich,
Birkhäuser, Basel, 2003.
 On the relative complexity of approximate counting problems
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum,
Algorithmica 38 (2004), 471500.
DOI 10.1007/s004530031073y
A preliminary version appeared in:
Approximation Algorithms for Combinatorial Optimization,
Springer LNCS 1913, 2000.

A bound on the capacity of backoff and acknowledgementbased protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan and Mike Paterson
SIAM Journal on Computing 33 (2004), 313331.
DOI 10.1137/S0097539700381851
A preliminary version appeared in: Proceedings of the 27th
Colloquium on Automata, Languages and Programming, 2000.
 A polynomialtime approximation algorithm
for the permanent of a matrix with
nonnegative entries
Mark Jerrum, Alistair Sinclair and Eric Vigoda,
Journal of the Association for Computing Machinery
(JACM), Volume 51 (2004), 671697.
DOI 10.1145/1008731.1008738
A preliminary version appeared in: Proceedings of the 33rd ACM Symposium on the
Theory of Computing, 2001.
 Counting and sampling Hcolourings
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Information and Computation 189 (2004), 116.
DOI 10.1016/j.ic.2003.09.001
A preliminary version appeared in: Proceedings of RANDOM'02.
 Elementary bounds on Poincaré and logSobolev constants
for decomposable Markov chains
Mark Jerrum, JungBae Son, Prasad Tetali and Eric Vigoda,
Annals of Applied Probability
14 (2004), 17411765.
DOI 10.1214/105051604000000639
 Rapidly mixing Markov chains
for dismantleable constraint graphs
Martin Dyer, Mark Jerrum and Eric Vigoda.
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science 63, AMS, 2004.
A preliminary version appeared in in:
Randomization and Approximation Techniques in Computer Science
(Proceedings of RANDOM'02),
Springer Lecture Notes in Computer Science 2483 (2002), 6877.
DOI 10.1007/3540457267_6
 On the approximation of one Markov chain by another
Mark Jerrum,
Probability Theory and Related Fields, 135 (2006), 114.
DOI
10.1007/s0044000504534
 Two remarks concerning balanced matroids
Mark Jerrum,
Combinatorica 26, 2006, 733742.
DOI 10.1007/s0049300600395
 Rapidly mixing Markov chains for sampling contingency tables
with a constant number of rows
Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin,
SIAM Journal on Computing 36 (2006), 247278.
DOI 10.1137/S0097539703434243
An extended abstract appeared in:
Proceedings of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS'02).
 Systematic scan for sampling colourings
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Annals of Applied Probability
16 (2006), 185230.
DOI 10.1214/105051605000000683
 Markov chain comparison
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin,
Probability Surveys 3 (2006), 89111.
Abstract
and link to full text.
 The complexity of ferromagnetic Ising with local fields
Leslie Ann Goldberg and Mark Jerrum,
Combinatorics, Probability and Computing 16 (2007), 4361.
DOI 10.1017/S096354830600767X
 Approximating the Tutte polynomial
Mark Jerrum, In Combinatorics and Probability: A Tribute to Dominic Welsh
(edited by Geoffrey Grimmett and Colin McDiarmid),
Oxford University Press, 2007.
Draft.
 Dobrushin conditions and systematic scan
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Combinatorics, Probability and Computing 17 (2008), 761779.
DOI 10.1017/S0963548308009437
A preliminary version appeared in:
Proc. 10th International Workshop on Randomization and Computation
(RANDOM).
 Inapproximability of the Tutte polynomial
Leslie Ann Goldberg and Mark Jerrum,
Information and Computation 206 (2008), 908929.
DOI 10.1016/j.ic.2008.04.003
An extended abstract appeared in: Proceedings of ACM STOC 2007.
 Matrix norms and rapid mixing for spin systems
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Annals of Applied Probability, 19 (2009), 71107.
DOI 10.1214/08AAP532

The complexity of weighted Boolean #CSP
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
SIAM Journal on Computing 38 (2009), 19701986.
DOI 10.1137/070690201

An approximation trichotomy for Boolean #CSP
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Journal of Computer and System Sciences 76 (2010), 267277.
DOI 10.1016/j.jcss.2009.08.003

A complexity dichotomy for hypergraph partition functions
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Computational Complexity 19 (2010), 605633.
DOI 10.1007/s0003701003006

The mixing time of Glauber dynamics for coloring regular trees
Leslie Ann Goldberg, Mark Jerrum and Marek Karpinski,
Random Structures and Algorithms 36 (2010), 464476
DOI 10.1002/rsa.20303

A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum and Marc Thurley,
SIAM Journal on Computing 39 (2010), 33363402.
DOI 10.1137/090757496
An extended abstract appeared in: Proc.
26th International Symposium on Theoretical Aspects of Computer Science
(STACS 2009).
DOI 10.4230/LIPIcs.STACS.2009.1821

The complexity of weighted and unweighted #CSP
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius,
Mark Jerrum and David Richerby,
Journal of Computer and System Sciences 78 (2012), 681688.
DOI 10.1016/j.jcss.2011.12.002

A counterexample to rapid mixing of the GeŠtefankovič Process
Leslie Ann Goldberg and Mark Jerrum,
Electronic Communications in Probability 17 (2012), no. 5, 16
DOI 10.1214/ECP.v171712

Inapproximability of the Tutte polynomial of a planar graph
Leslie Ann Goldberg and Mark Jerrum,
Computational Complexity 21 (2012), 605642.
DOI 10.1007/s0003701200464

Approximating the partition function of the ferromagnetic Potts model
Leslie Ann Goldberg and Mark Jerrum,
Journal of the ACM 59 (2012).
DOI 10.1145/2371656.2371660
An extended abstract appeared in:
Proc. 37th International Colloquium on Automata Languages and Programming
(ICALP 2010).
DOI 10.1007/9783642141652_34

Approximating the Tutte polynomial of a binary matroid
and other related combinatorial polynomials
Leslie Ann Goldberg and Mark Jerrum,
Journal of Computer and System Sciences 79 (2013), 6878.
DOI 10.1016/j.jcss.2012.04.005

A polynomialtime algorithm for estimating the partition function
of the ferromagnetic Ising model on a regular matroid
Leslie Ann Goldberg and Mark Jerrum,
SIAM Journal on Computing 42 (2013), 1132–1157.
DOI 10.1137/110851213
An extended abstract appeared in:
Proc. 38th International Colloquium on Automata Languages and Programming
(ICALP 2011).
DOI 10.1007/9783642220067_44

The expressibility of functions on the Boolean domain, with applications to counting CSPs
Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Colin McQuillan.
Journal of the ACM 60(5) (2013).
DOI 10.1145/2528401
An extended abstract appeared under the title
"Logsupermodular functions, functional clones and counting CSPs" in:
Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012).
DOI 10.4230/LIPIcs.STACS.2012.302

The complexity of approximately counting tree homomorphisms
Leslie Ann Goldberg and Mark Jerrum,
ACM Transactions on Computation Theory 6(2) (2014).
DOI 10.1145/2600917

The complexity of computing the sign of the Tutte polynomial
Leslie Ann Goldberg and Mark Jerrum,
SIAM Journal on Computing 436 (2014), 1921–1952.
DOI 10.1137/12088330X.
Download PDF.
An extended abstract with a longer title appeared in:
Proc. 39th International Colloquium on Automata Languages and Programming
(ICALP 2012).
DOI 10.1007/9783642315947_34

The parameterised complexity of counting connected subgraphs and graph motifs
Mark Jerrum and Kitty Meeks,
Journal of Computer and System Sciences 81(4) (2015), 702–716.
DOI 10.1016/j.jcss.2014.11.015

Approximating the partition function of planar twostate spin systems
Leslie Ann Goldberg, Mark Jerrum and Colin McQuillan,
Journal of Computer and System Sciences,
81(1) (2015), 330–358.
DOI 10.1016/j.jcss.2014.06.007

The complexity of approximating conservative counting CSPs
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan and David Richerby,
Journal of Computer and System Sciences 81(1) (2015), 311–329.
DOI 10.1016/j.jcss.2014.06.006

The complexity of parity graph homomorphism: an initial investigation
John Faben and Mark Jerrum,
Theory of Computing 11 (2015), Article 2, 35–57.
DOI 10.4086/toc.2015.v011a002

Some hard families of parameterised counting problems
Mark Jerrum and Kitty Meeks, ACM Transactions on Computation Theory 7(3) (2015), Article 11.
DOI 10.1145/2786017

A complexity classification of spin systems with an external field
Leslie Ann Goldberg and Mark Jerrum,
Proceedings of the National Academy of Sciences (PNAS) 112(43) (2015), 13161–13166.
DOI 10.1073/pnas.1505664112

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Leslie Ann Goldberg and Mark Jerrum,
Theoretical Computer Science, 634 (2016), 35–46.
DOI 10.1016/j.tcs.2016.04.008
A preliminary version appeared with a different title as
arXiv:1509.03543v1

Random cluster dynamics for the Ising model is rapidly mixing
Heng Guo and Mark Jerrum, April 2016.
arXiv:1605.00139
An extended abstract appeared in: Proceedings of the 28th Annual
ACMSIAM Symposium on Discrete Algorithms (SODA '17), SIAM,
Barcelona, Spain, 1818–1827.
DOI 10.1137/1.9781611974782.118

#BIShardness for 2spin systems on bipartite bounded degree graphs
in the tree nonuniqueness region
JinYi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum,
Daniel Štefankovič and Eric Vigoda,
Journal of Computer and System Sciences, 82 Issue 5 (2016), 690–711.
DOI 10.1016/j.jcss.2015.11.009
An extended abstract appeared in:
Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
(APPROX/RANDOM 2014).
DOI 10.4230/LIPIcs.APPROXRANDOM.2014.582

Approximately counting Hcolourings is #BISHard
Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum,
SIAM Journal on Computing 45(3) (2016), 680–711.
DOI 10.1137/15M1020551
An extended abstract appeared in:
Proc. International Colloquium on Automata Languages and Programming (ICALP) 2015.
DOI 10.1007/9783662476727_43

The parameterised complexity of counting even and odd induced subgraphs
Mark Jerrum and Kitty Meeks,
Combinatorica (2016).
DOI 10.1007/s0049301633385

Uniform sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum and Jingcheng Liu, November 2016.
arXiv:1611.01647
An extended abstract appeared in: Proceedings of the 49th Annual
ACM Symposium on Theory of Computing (STOC '17), 342–355.
DOI 10.1145/3055399.3055410

Counting Constraint Satisfaction Problems
In "The Constraint Satisfaction Problem: Complexity and Approximability",
Dagstuhl FollowUps, vol 7, Schloss Dagstuhl  LeibnizZentrum für Informatik (2017), 205–231.
DOI 10.4230/DFU.Vol7.15301.205

A complexity trichotomy for approximately counting list Hcolourings
Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum,
ACM Transactions on Computation Theory 9(2) (2017),
Article 9.
DOI 10.1145/3037381.
An extended abstract appeared in:
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
DOI 10.4230/LIPIcs.ICALP.2016.46

On the switch Markov chain for perfect matchings
Martin Dyer, Mark Jerrum and Haiko Müller,
Journal of the ACM 64(2) (2017), Article 12.
DOI 10.1145/2822322.
An extended abstract appeared in: Proceedings of the 27th Annual
ACMSIAM Symposium on Discrete Algorithms (SODA '16), SIAM,
Philadelphia, PA, 1972–1983.
DOI 10.1137/1.9781611974331.ch138

Functional clones and expressibility of partition functions
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby and Stanislav Živný,
Theoretical Computer Science 687 (2017), 11–39.
DOI 10.1016/j.tcs.2017.05.001

Random walks on small world networks
Martin Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum and Eric Vigoda, July 2017.
arXiv:1707.02467

A polynomialtime approximation algorithm for allterminal network reliability
Heng Guo and Mark Jerrum, February 2018.
arXiv:1709.08561
(A revised version of an arXiv posting dated September 2017.)

Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
Heng Guo and Mark Jerrum, January 2018.
arXiv:1801.07342