Prof Mark Jerrum
Professor of Mathematics
School of Mathematical Sciences
Queen Mary University of London
Queen Mary University of London
Research
Applied probability, Combinatorics, Theoretical computer science
Interests
I am interested combinatorics, computational complexity and stochastic processes. All of these ingredients come together in the study of randomised algorithms: computational procedures that exploit the surprising power of making random choices. A strong theme in this work is the analysis of the mixing time of combinatorially or geometrically defined Markov chains. More generally, I work on the computational complexity of counting problems, including weighted counted problems as exemplified by partition functions and generating functions. Statistical physics, Constraint Satisfaction Problems and graph polynomials provide a rich source of motivating examples.Publications
Publications of specific relevance to the Centre for Combinatorics, Algebra and Number Theory2024
Fundamentals of Partial Rejection SamplingJerrum M
Probability Surveys, Institute of Mathematical Statistics
03-09-2024
Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixingAnand K and Jerrum M
Annales De L’Institut Henri Poincaré D Combinatorics Physics and Their Interactions, European Mathematical Society - Ems - Publishing House
02-08-2024
2023
A simple polynomial-time approximation algorithm for the total variation distance between two product distributionsJerrum M, Guo H, Wang J and Feng W
Theoretics, Episciences
15-06-2023
2022
Perfect Sampling in Infinite Spin Systems Via Strong Spatial MixingAnand K and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 51 (4), 1280-1295.
26-07-2022
Counting vertices of integral polytopes defined by facetsGuo H and Jerrum M
Discrete and Computational Geometry, Springer
05-07-2022
2021
Counting weighted independent sets beyond the permanentJerrum M, Dyer M, Müller H and Vušković K
Siam Journal on Discrete Mathematics, Society For Industrial and Applied Mathematics vol. 35 (2), 1503-1524.
24-06-2021
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphsJerrum M, Dyer M, Heinrich M and Müller H
Combinatorics, Probability and Computing, Cambridge University Press (Cup)
12-04-2021
The Size of the Giant Joint Component in a Binomial Random Double GraphJerrum M and Makai T
The Electronic Journal of Combinatorics vol. 28 (1)
12-02-2021
Sharp thresholds of graph properties, and the k-sat problemJerrum MR
Bulletin of The American Mathematical Society vol. 58 (2), 267-268.
01-01-2021
2020
Random Walks on Small World NetworksJerrum M, Galanis A, Goldberg LA, Vigoda E and Dyer M
Acm Transactions on Algorithms, Association For Computing Machinery vol. 16 (3)
01-06-2020
2019
Approximating Pairwise Correlations in the Ising ModelJerrum M and Goldberg LA
Acm Transactions on Computation Theory, Association For Computing Machinery vol. 11 (4)
01-07-2019
A Polynomial-Time Approximation Algorithm for All-Terminal Network ReliabilityGuo H and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 48 (3), 964-978.
09-05-2019
Uniform Sampling Through the Lovász Local LemmaGuo H, Jerrum M and Liu J
Journal of The Acm, Association For Computing Machinery (Acm) vol. 66 (3), 1-31.
12-04-2019
2018
Perfect simulation of the hard disks model by partial rejection samplingGuo H and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 107
01-07-2018
A polynomial-time approximation algorithm for all-terminal network reliabilityGuo H and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 107
01-07-2018
Random cluster dynamics for the Ising model is rapidly mixingGuo H and JERRUM MR
Annals of Applied Probability, Institute of Mathematical Statistics
11-04-2018
2017
The parameterised complexity of counting even and odd induced subgraphsJerrum M and Meeks K
Combinatorica vol. 37 (5), 965-990.
01-10-2017
Uniform sampling through the Lovász Local LemmaGuo H, Jerrum M and Liu J
STOC’17, Montreal, Canada. vol. Part F128415, 342-355.
19-06-2017
On the switch Markov chain for perfect matchingsDyer M, JERRUM MR and Müller H
Journal of The Association For Computing Machinery (Acm), Association For Computing Machinery vol. 64 (2)
12-05-2017
Functional clones and expressibility of partition functionsBulatov A, Goldberg LA, Jerrum M, Richerby D and Živný S
Theoretical Computer Science
11-05-2017
A complexity trichotomy for approximately counting list H-colouringsJERRUM MR, Galanis A and Goldberg LA
Acm Transactions on Computation Theory, Association For Computing Maachinery vol. 9 (2)
01-05-2017
Counting Constraint Satisfaction Problems.Jerrum M
In The Constraint Satisfaction Problem, Schloss Dagstuhl - Leibniz-Zentrum FüR Informatik 205-231. Editors: Krokhin AA and Zivný S.
01-01-2017
2016
A complexity trichotomy for approximately counting list H-colouringsGalanis A, Goldberg LA and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 55
01-08-2016
The complexity of counting locally maximal satisfying assignments of Boolean CSPsGoldberg LA and Jerrum M
Theoretical Computer Science, Elsevier vol. 634, 35-46.
01-06-2016
APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARDGalanis A, Goldberg LA and Jerrum M
Siam Journal on Computing vol. 45 (3), 680-711.
19-05-2016
2015
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness regionCai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D and Vigoda E
Journal of Computer and System Sciences vol. 82 (5), 690-711.
02-12-2015
A complexity classification of spin systems with an external field.Goldberg LA and Jerrum M
Proceedings of The National Academy of Sciences of The United States of America vol. 112 (43), 13161-13166.
01-10-2015
Some Hard Families of Parameterized Counting ProblemsJerrum M and Meeks K
Acm Transactions on Computation Theory, Association For Computing Machinery (Acm) vol. 7 (3), 1-18.
09-07-2015
The complexity of parity graph homomorphism: An initial investigationFaben J and Jerrum M
Theory of Computing vol. 11, 35-57.
14-03-2015
The complexity of approximating conservative counting CSPsChen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D
Journal of Computer and System Sciences vol. 81 (1), 311-329.
01-02-2015
Approximately Counting H-Colourings is #BIS-HardGalanis A, Goldberg LA and Jerrum M
Lecture Notes in Computer Science. vol. 9134, 529-541.
01-01-2015
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard.Galanis A, Goldberg LA and Jerrum M
ICALP (1). vol. 9134, 529-541. Editors: Halldórsson MM, Iwama K, Kobayashi N and Speckmann B.
01-01-2015
Approximating the partition function of planar two-state spin systems.Goldberg LA, Jerrum M and McQuillan C
J. Comput. Syst. Sci. vol. 81, 330-358.
01-01-2015
2014
The parameterised complexity of counting connected subgraphs and graph motifsJerrum M and Meeks K
Journal of Computer and System Sciences vol. 81 (4), 702-716.
24-11-2014
BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness regionCai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D and Vigoda E
Leibniz International Proceedings in Informatics, LIPIcs. vol. 28, 582-595.
01-09-2014
The Complexity of Approximately Counting Tree HomomorphismsGoldberg LA and Jerrum M
Acm Transactions on Computation Theory, Association For Computing Machinery (Acm) vol. 6 (2), 1-31.
01-05-2014
The Complexity of Computing the Sign of the Tutte PolynomialGoldberg LA and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 43 (6), 1921-1952.
01-01-2014
2013
The expressibility of functions on the Boolean domain, with applications to Counting CSPsBulatov A, Dyer M, Goldberg LA, Jerrum M and McQuillan C
J. Assoc. Comput. Mach., Acm Digital Library vol. 60 (5)
01-10-2013
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomialsGoldberg LA and Jerrum M
Journal of Computer and System Sciences vol. 79 (1), 68-78.
01-01-2013
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.Goldberg LA and Jerrum M
Siam J. Comput. vol. 42, 1132-1157.
01-01-2013
The complexity of approximating conservative counting CSPs.Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D
STACS. vol. 20, 148-159. Editors: Portier N and Wilke T.
01-01-2013
2012
A counterexample to rapid mixing of the Ge-Stefankovic processGoldberg LA and Jerrum M
Electronic Communications in Probability vol. 17, 1-6.
01-01-2012
The complexity of weighted and unweighted #CSPBulatov A, Dyer M, Goldberg LA, Jalsenius M, Jerrum M and Richerby D
Journal of Computer and System Sciences vol. 78 (2), 681-688.
01-01-2012
Inapproximability of the Tutte polynomial of a planar graphGoldberg LA and Jerrum M
Computational Complexity vol. 21 (4), 605-642.
01-01-2012
Approximating the Partition Function of the Ferromagnetic Potts ModelGoldberg LA and Jerrum M
Journal of The Acm vol. 59 (5)
01-01-2012
Approximating the partition function of planar two-state spin systemsGoldberg LA, Jerrum M and McQuillan C
Corr vol. abs/1208.4987
01-01-2012
Log-supermodular functions, functional clones and counting CSPs.Bulatov AA, Dyer ME, Goldberg LA and Jerrum M
STACS. vol. 14, 302-313. Editors: Dürr C and Wilke T.
01-01-2012
The complexity of approximating conservative counting CSPsChen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D
Corr vol. abs/1208.1783
01-01-2012
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation).Goldberg LA and Jerrum M
ICALP (1). vol. 7391, 399-410. Editors: Czumaj A, Mehlhorn K, Pitts AM and Wattenhofer R.
01-01-2012
2011
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.Goldberg LA and Jerrum M
ICALP (1). vol. 6755, 521-532. Editors: Aceto L, Henzinger M and Sgall J.
01-01-2011
2010
A Complexity Dichotomy For Hypergraph Partition FunctionsDyer M, Goldberg LA and Jerrum M
Comput Complex vol. 19 (4), 605-633.
01-12-2010
Technical Perspective Constraint Satisfaction Problems and Computational ComplexityJerrum M
Commun Acm vol. 53 (9), 98-98.
01-09-2010
The Mixing Time of Glauber Dynamics for Coloring Regular TreesGoldberg LA, Jerrum M and Karpinski M
Random Struct Algor vol. 36 (4), 464-476.
01-07-2010
An approximation trichotomy for Boolean #CSPDyer M, Goldberg LA and Jerrum M
J Comput Syst Sci vol. 76 (3-4), 267-277.
01-05-2010
Approximating the Partition Function of the Ferromagnetic Potts ModelGoldberg LA and Jerrum M
AUTOMATA, LANGUAGES AND PROGRAMMING, PT I. vol. 6198, 396-407. Editors: Abramsky S, Gavoille C, Kirchner C, MeyerAufDerHeide F and Spirakis PG.
01-01-2010
Approximating the Partition Function of the Ferromagnetic Potts Model.Goldberg LA and Jerrum M
ICALP (1). vol. 6198, 396-407. Editors: Abramsky S, Gavoille C, Kirchner C, Heide FMAD and Spirakis PG.
01-01-2010
A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH MIXED SIGNSGoldberg LA, Grohe M, Jerrum M and Thurley M
Siam J Comput vol. 39 (7), 3336-3402.
01-01-2010
2009
MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMSDyer M, Goldberg LA and Jerrum M
Ann Appl Probab vol. 19 (1), 71-107.
01-02-2009
A Complexity Dichotomy for Partition Functions with Mixed Signs.Goldberg LA, Grohe M, Jerrum M and Thurley M
STACS. vol. 3, 493-504. Editors: Albers S and Marion J-Y.
01-01-2009
2008
Dobrushin Conditions and Systematic ScanDyer M, Goldberg LA and Jerrum M
Comb Probab Comput vol. 17 (6), 761-779.
01-11-2008
Inapproximability of the Tutte polynomialGoldberg LA and Jerrum M
Inform Comput vol. 206 (7), 908-929.
01-07-2008
THE COMPLEXITY OF WEIGHTED BOOLEAN #CSPDyer M, Goldberg LA and Jerrum M
Siam J Comput vol. 38 (5), 1970-1986.
01-01-2008
2007
Inapproximability of the Tutte polynomial.Goldberg LA and Jerrum M
STOC., 459-468. Editors: Johnson DS and Feige U.
01-01-2007
Inapproximability of the Tutte PolynomialGoldberg LA and Jerrum M
STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING., 459-468.
01-01-2007
The complexity of ferromagnetic ising with local fieldsGoldberg LA and Jerrum M
Comb Probab Comput vol. 16 (1), 43-61.
01-01-2007
2006
On the approximation of one Markov chain by anotherJerrum M
Probab Theory Rel vol. 135 (1), 1-14.
01-05-2006
Systematic scan for sampling coloringsDyer M, Goldberg LA and Jerrum M
Ann Appl Probab vol. 16 (1), 185-230.
01-02-2006
Dobrushin Conditions and Systematic Scan.Dyer ME, Goldberg LA and Jerrum M
APPROX-RANDOM. vol. 4110, 327-338. Editors: Díaz J, Jansen K, Rolim JDP and Zwick U.
01-01-2006
Dobrushin conditions and systematic scanDyer M, Goldberg LA and Jerrum M
APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES. vol. 4110, 327-338. Editors: Draz J, Jansen K, Rolim JDP and Zwick U.
01-01-2006
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rowsCryan M, Dyer M, Goldberg LA, Jerrum M and Martin R
Siam J Comput vol. 36 (1), 247-278.
01-01-2006
Markov chain comparisonJERRUM MR, Martin R, Dyer M and Goldberg LA
Probability Surveys vol. 3, 89-111.
01-01-2006
2004
Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chainsJerrum M, Son JB, Tetali P and Vigoda E
Ann Appl Probab vol. 14 (4), 1741-1765.
01-11-2004
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJerrum M, Sinclair A and Vigoda E
J Acm vol. 51 (4), 671-697.
01-07-2004
Special issue on Isaac Newton Institute Programme - Computation, combinatorics and probability: Part I - PrefaceDyer M, Jerrum M and Winkler P
Random Struct Algor vol. 24 (3), 233-233.
01-05-2004
The relative complexity of approximate counting problemsDyer M, Goldberg LA, Greenhill C and Jerrum M
Algorithmica vol. 38 (3), 471-500.
01-03-2004
Counting and sampling H-colouringsDyer M, Goldberg LA and Jerrum M
Inform Comput vol. 189 (1), 1-16.
25-02-2004
A bound on the capacity of backoff and acknowledgment-based protocolsGoldberg LA, Jerrum M, Kannan S and Paterson M
Siam J Comput vol. 33 (2), 313-331.
01-01-2004
2003
The computational complexity of two-state spin systemsGoldberg LA, Jerrum M and Paterson M
Random Struct Algor vol. 23 (2), 133-154.
01-09-2003
2002
On counting independent sets in sparse graphsDyer M, Frieze A and Jerrum M
SIAM JOURNAL ON COMPUTING. vol. 31 (5), 1527-1541.
15-08-2002
Convergence of the iterated prisoner's dilemma gameDyer M, Goldberg LA, Greenhill C, Istrate G and Jerrum M
Comb Probab Comput vol. 11 (2), 135-147.
01-03-2002
The 'Burnside process' converges slowlyGoldberg LA and Jerrum M
Comb Probab Comput vol. 11 (1), 21-34.
01-01-2002
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rowsCryan M, Dyer M, Goldberg LA, Jerrum M and Martin R
FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 711-720.
01-01-2002
Counting and Sampling H-Colourings.Dyer ME, Goldberg LA and Jerrum M
RANDOM. vol. 2483, 51-67. Editors: Rolim JDP and Vadhan SP.
01-01-2002
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.Dyer ME, Jerrum M and Vigoda E
RANDOM. vol. 2483, 68-77. Editors: Rolim JDP and Vadhan SP.
01-01-2002
Spectral gap and log-Sobolev constant for balanced matroidsJerrum M and Son JB
FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 721-729.
01-01-2002
2001
An extension of path coupling and its application to the Glauber dynamics for graph coloringsDyer M, Goldberg LA, Greenhill C, Jerrum M and Mitzenmacher M
Siam J Comput vol. 30 (6), 1962-1975.
01-01-2001
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.Jerrum M, Sinclair A and Vigoda E
STOC., 712-721. Editors: Vitter JS, Spirakis PG and Yannakakis M.
01-01-2001
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.Dyer ME, Jerrum M and Vigoda E
Graphs, Morphisms and Statistical Physics. vol. 63, 87-95. Editors: Nesetril J and Winkler P.
01-01-2001
2000
Randomly Sampling MoleculesGoldberg LA and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 29 (3), 834-853.
01-01-2000
Counting Unlabelled Subtrees of a Tree is #P-completeGoldberg LA and Jerrum M
Lms Journal of Computation and Mathematics, Wiley vol. 3, 117-124.
01-01-2000
1999
The Swendsen–Wang Process Does Not Always Mix RapidlyGore VK and Jerrum MR
Journal of Statistical Physics, Springer Nature vol. 97 (1-2), 67-86.
01-10-1999
On Approximately Counting Colorings of Small Degree GraphsBubley R, Dyer M, Greenhill C and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 29 (2), 387-400.
01-01-1999
1998
Approximately Counting Hamilton Paths and Cycles in Dense GraphsDyer M, Frieze A and Jerrum M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 27 (5), 1262-1272.
01-10-1998
An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical NetworksGoldberg LA, Jerrum M and MacKenzie PD
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 27 (4), 1083-1098.
01-08-1998
An elementary analysis of a procedure for sampling points in a convex bodyBubley R, Dyer M and Jerrum M
Random Structures and Algorithms, Wiley vol. 12 (3), 213-235.
01-05-1998
The Metropolis algorithm for graph bisectionJerrum M and Sorkin GB
Discrete Applied Mathematics, Elsevier vol. 82 (1-3), 155-175.
01-03-1998
1997
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel ComputersGoldberg LA, Jerrum M, Leighton T and Rao S
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 26 (4), 1100-1119.
01-08-1997
Improved approximation algorithms for MAXk-CUT and MAX BISECTIONFrieze A and Jerrum M
Algorithmica, Springer Nature vol. 18 (1), 67-81.
01-05-1997
1995
A very simple algorithm for estimating the number of k‐colorings of a low‐degree graphJerrum M
Random Structures and Algorithms, Wiley vol. 7 (2), 157-165.
01-09-1995
1994
Simple Translation-Invariant Concepts Are Hard to LearnJerrum M
Information and Computation, Elsevier vol. 113 (2), 300-311.
01-09-1994
Counting trees in a graph is #P-completeJerrum M
Information Processing Letters, Elsevier vol. 51 (3), 111-116.
01-08-1994
Three-dimensional Statistical Data Security ProblemsIrving RW and Jerrum MR
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 23 (1), 170-184.
01-02-1994
1993
Polynomial-Time Approximation Algorithms for the Ising ModelJerrum M and Sinclair A
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 22 (5), 1087-1116.
01-10-1993
1992
Large Cliques Elude the Metropolis ProcessJerrum M
Random Structures and Algorithms, Wiley vol. 3 (4), 347-359.
01-01-1992
1990
Fast uniform generation of regular graphsJerrum M and Sinclair A
Theoretical Computer Science, Elsevier vol. 73 (1), 91-100.
01-06-1990
Two-dimensional monomer-dimer systems are computationally intractableJerrum M
Journal of Statistical Physics, Springer Nature vol. 59 (3-4), 1087-1088.
01-05-1990
1989
Approximating the PermanentJerrum M and Sinclair A
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 18 (6), 1149-1178.
01-12-1989
Approximate counting, uniform generation and rapidly mixing Markov chainsSinclair A and Jerrum M
Information and Computation, Elsevier vol. 82 (1), 93-133.
01-07-1989
1987
Two-dimensional monomer-dimer systems are computationally intractableJerrum M
Journal of Statistical Physics, Springer Nature vol. 48 (1-2), 121-134.
01-07-1987
1986
A compact representation for permutation groupsJerrum M
Journal of Algorithms, Elsevier vol. 7 (1), 60-78.
01-03-1986
Random generation of combinatorial structures from a uniform distributionJerrum MR, Valiant LG and Vazirani VV
Theoretical Computer Science, Elsevier vol. 43, 169-188.
01-01-1986
1985
The complexity of finding minimum-length generator sequencesJerrum MR
Theoretical Computer Science, Elsevier vol. 36, 265-289.
01-01-1985
1984
Families of Fixed Degree Graphs for Processor InterconnectionJerrum MR and Skyum S
Ieee Transactions on Computers, Institute of Electrical and Electronics Engineers (Ieee) vol. C-33 (2), 190-194.
01-02-1984
1982
Some Exact Complexity Results for Straight-Line Computations over SemiringsJerrum M and Snir M
Journal of The Acm, Association For Computing Machinery (Acm) vol. 29 (3), 874-897.
01-07-1982
Grants
Grants of specific relevance to the Centre for Combinatorics, Algebra and Number TheoryMaths Research Associates 2021Mark Jerrum
£400,000 EPSRC Engineering and Physical Sciences Research Council
01-01-2021 - 30-09-2023
Sampling in Hereditary Classes - lead site University of LeedsMark Jerrum
£78,310 EPSRC Engineering and Physical Sciences Research Council
01-04-2019 - 31-07-2023
Algorithms That CountMark Jerrum
£361,972 EPSRC Engineering and Physical Sciences Research Council
01-11-2015 - 30-04-2019