Prof Mark Jerrum

Professor of Mathematics

School of Mathematical Sciences
Queen Mary University of London

m.jerrum@qmul.ac.uk

www.maths.qmul.ac.uk/~mj/

Centre for Combinatorics, Algebra and Number Theory

Research
Publications
Grants

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 Theory

2024

Fundamentals of Partial Rejection Sampling
Jerrum M
Probability Surveys, Institute of Mathematical Statistics

DOI 10.1214/24-PS29

QMRO

03-09-2024

Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixing
Anand K and Jerrum M
Annales De L’Institut Henri Poincaré D Combinatorics Physics and Their Interactions, European Mathematical Society - Ems - Publishing House

DOI 10.4171/aihpd/195

QMRO

02-08-2024

2023

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
Jerrum M, Guo H, Wang J and Feng W
Theoretics, Episciences

DOI 10.46298/theoretics.23.7

QMRO

15-06-2023

2022

Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
Anand K and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 51 (4), 1280-1295.

DOI 10.1137/21m1437433

QMRO

26-07-2022

Counting vertices of integral polytopes defined by facets
Guo H and Jerrum M
Discrete and Computational Geometry, Springer

DOI 10.1007/s00454-022-00406-8

QMRO

05-07-2022

2021

Counting weighted independent sets beyond the permanent
Jerrum 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.

DOI 10.1137/20M1347747

QMRO

24-06-2021

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
Jerrum M, Dyer M, Heinrich M and Müller H
Combinatorics, Probability and Computing, Cambridge University Press (Cup)

DOI 10.1017/S0963548321000080

QMRO

12-04-2021

The Size of the Giant Joint Component in a Binomial Random Double Graph
Jerrum M and Makai T
The Electronic Journal of Combinatorics vol. 28 (1)

DOI 10.37236/8846

QMRO

12-02-2021

Sharp thresholds of graph properties, and the k-sat problem
Jerrum MR
Bulletin of The American Mathematical Society vol. 58 (2), 267-268.
01-01-2021

2020

Random Walks on Small World Networks
Jerrum M, Galanis A, Goldberg LA, Vigoda E and Dyer M
Acm Transactions On Algorithms, Association For Computing Machinery vol. 16 (3)

DOI 10.1145/3403658

QMRO

01-06-2020

2019

Approximating Pairwise Correlations in the Ising Model
Jerrum M and Goldberg LA
Acm Transactions On Computation Theory, Association For Computing Machinery vol. 11 (4)

DOI 10.1145/3337785

QMRO

01-07-2019

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
Guo H and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 48 (3), 964-978.

DOI 10.1137/18m1201846

QMRO

09-05-2019

Uniform Sampling Through the Lovász Local Lemma
Guo H, Jerrum M and Liu J
Journal of The Acm, Association For Computing Machinery (Acm) vol. 66 (3), 1-31.

DOI 10.1145/3310131

QMRO

12-04-2019

2018

Perfect simulation of the hard disks model by partial rejection sampling
Guo H and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 107

DOI 10.4230/LIPIcs.ICALP.2018.69

01-07-2018

A polynomial-time approximation algorithm for all-terminal network reliability
Guo H and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 107

DOI 10.4230/LIPIcs.ICALP.2018.68

01-07-2018

Random cluster dynamics for the Ising model is rapidly mixing
Guo H and JERRUM MR
Annals of Applied Probability, Institute of Mathematical Statistics

DOI 10.1214/17-AAP1335

QMRO

11-04-2018

2017

The parameterised complexity of counting even and odd induced subgraphs
Jerrum M and Meeks K
Combinatorica vol. 37 (5), 965-990.

DOI 10.1007/s00493-016-3338-5

QMRO

01-10-2017

Uniform sampling through the Lovász Local Lemma
Guo H, Jerrum M and Liu J
STOC’17, Montreal, Canada. vol. Part F128415, 342-355.

DOI 10.1145/3055399.3055410

QMRO

19-06-2017

On the switch Markov chain for perfect matchings
Dyer M, JERRUM MR and Müller H
Journal of The Association For Computing Machinery (Acm), Association For Computing Machinery vol. 64 (2)

DOI 10.1145/2822322

QMRO

12-05-2017

Functional clones and expressibility of partition functions
Bulatov A, Goldberg LA, Jerrum M, Richerby D and Živný S
Theoretical Computer Science

DOI 10.1016/j.tcs.2017.05.001

QMRO

11-05-2017

A complexity trichotomy for approximately counting list H-colourings
JERRUM MR, Galanis A and Goldberg LA
Acm Transactions On Computation Theory, Association For Computing Maachinery vol. 9 (2)

DOI 10.1145/3037381

QMRO

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-colourings
Galanis A, Goldberg LA and Jerrum M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 55

DOI 10.4230/LIPIcs.ICALP.2016.46

01-08-2016

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Goldberg LA and Jerrum M
Theoretical Computer Science, Elsevier vol. 634, 35-46.

DOI 10.1016/j.tcs.2016.04.008

QMRO

01-06-2016

APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD
Galanis A, Goldberg LA and Jerrum M
Siam Journal On Computing vol. 45 (3), 680-711.

DOI 10.1137/15M1020551

QMRO

19-05-2016

2015

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Cai 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.

DOI 10.1016/j.jcss.2015.11.009

QMRO

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.

DOI 10.1073/pnas.1505664112

01-10-2015

Some Hard Families of Parameterized Counting Problems
Jerrum M and Meeks K
Acm Transactions On Computation Theory, Association For Computing Machinery (Acm) vol. 7 (3), 1-18.

DOI 10.1145/2786017

09-07-2015

The complexity of parity graph homomorphism: An initial investigation
Faben J and Jerrum M
Theory of Computing vol. 11, 35-57.

DOI 10.4086/toc.2015.v011a002

14-03-2015

The complexity of approximating conservative counting CSPs
Chen 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.

DOI 10.1016/j.jcss.2014.06.006

QMRO

01-02-2015

Approximately Counting H-Colourings is #BIS-Hard
Galanis A, Goldberg LA and Jerrum M
Lecture Notes in Computer Science. vol. 9134, 529-541.

DOI 10.1007/978-3-662-47672-7_43

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.

DOI 10.1016/j.jcss.2014.06.007

01-01-2015

2014

The parameterised complexity of counting connected subgraphs and graph motifs
Jerrum M and Meeks K
Journal of Computer and System Sciences vol. 81 (4), 702-716.

DOI 10.1016/j.jcss.2014.11.015

QMRO

24-11-2014

BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D and Vigoda E
Leibniz International Proceedings in Informatics, LIPIcs. vol. 28, 582-595.

DOI 10.4230/LIPIcs.APPROX-RANDOM.2014.582

01-09-2014

The Complexity of Approximately Counting Tree Homomorphisms
Goldberg LA and Jerrum M
Acm Transactions On Computation Theory, Association For Computing Machinery (Acm) vol. 6 (2), 1-31.

DOI 10.1145/2600917

01-05-2014

The Complexity of Computing the Sign of the Tutte Polynomial
Goldberg LA and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 43 (6), 1921-1952.

DOI 10.1137/12088330x

QMRO

01-01-2014

2013

The expressibility of functions on the Boolean domain, with applications to Counting CSPs
Bulatov A, Dyer M, Goldberg LA, Jerrum M and McQuillan C
J. Assoc. Comput. Mach., Acm Digital Library vol. 60 (5)

DOI 10.1145/2528401

QMRO

01-10-2013

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
Goldberg LA and Jerrum M
Journal of Computer and System Sciences vol. 79 (1), 68-78.

DOI 10.1016/j.jcss.2012.04.005

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.

DOI 10.1137/110851213

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 process
Goldberg LA and Jerrum M
Electronic Communications in Probability vol. 17, 1-6.

DOI 10.1214/ECP.v17-1712

01-01-2012

The complexity of weighted and unweighted #CSP
Bulatov A, Dyer M, Goldberg LA, Jalsenius M, Jerrum M and Richerby D
Journal of Computer and System Sciences vol. 78 (2), 681-688.

DOI 10.1016/j.jcss.2011.12.002

01-01-2012

Inapproximability of the Tutte polynomial of a planar graph
Goldberg LA and Jerrum M
Computational Complexity vol. 21 (4), 605-642.

DOI 10.1007/s00037-012-0046-4

01-01-2012

Approximating the Partition Function of the Ferromagnetic Potts Model
Goldberg LA and Jerrum M
Journal of The Acm vol. 59 (5)

DOI 10.1145/2371656.2371660

01-01-2012

Approximating the partition function of planar two-state spin systems
Goldberg LA, Jerrum M and McQuillan C
Corr vol. abs/1208.4987

DOI 10.1016/j.jcss.2014.06.007

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 CSPs
Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D
Corr vol. abs/1208.1783

DOI 10.4230/LIPIcs.STACS.2013.148

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 Functions
Dyer M, Goldberg LA and Jerrum M
Comput Complex vol. 19 (4), 605-633.

DOI 10.1007/s00037-010-0300-6

01-12-2010

Technical Perspective Constraint Satisfaction Problems and Computational Complexity
Jerrum M
Commun Acm vol. 53 (9), 98-98.

DOI 10.1145/1810891.1810913

01-09-2010

The Mixing Time of Glauber Dynamics for Coloring Regular Trees
Goldberg LA, Jerrum M and Karpinski M
Random Struct Algor vol. 36 (4), 464-476.

DOI 10.1002/rsa.20303

01-07-2010

An approximation trichotomy for Boolean #CSP
Dyer M, Goldberg LA and Jerrum M
J Comput Syst Sci vol. 76 (3-4), 267-277.

DOI 10.1016/j.jcss.2009.08.003

01-05-2010

Approximating the Partition Function of the Ferromagnetic Potts Model
Goldberg 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.

DOI 10.1007/978-3-642-14165-2_34

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 SIGNS
Goldberg LA, Grohe M, Jerrum M and Thurley M
Siam J Comput vol. 39 (7), 3336-3402.

DOI 10.1137/090757496

01-01-2010

2009

MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS
Dyer M, Goldberg LA and Jerrum M
Ann Appl Probab vol. 19 (1), 71-107.

DOI 10.1214/08-AAP532

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 Scan
Dyer M, Goldberg LA and Jerrum M
Comb Probab Comput vol. 17 (6), 761-779.

DOI 10.1017/S0963548308009437

01-11-2008

Inapproximability of the Tutte polynomial
Goldberg LA and Jerrum M
Inform Comput vol. 206 (7), 908-929.

DOI 10.1016/j.ic.2008.04.003

01-07-2008

THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP
Dyer M, Goldberg LA and Jerrum M
Siam J Comput vol. 38 (5), 1970-1986.

DOI 10.1137/070690201

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 Polynomial
Goldberg LA and Jerrum M
STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING., 459-468.

DOI 10.1145/1250790.1250858

01-01-2007

The complexity of ferromagnetic ising with local fields
Goldberg LA and Jerrum M
Comb Probab Comput vol. 16 (1), 43-61.

DOI 10.1017/S096354830600767X

01-01-2007

2006

On the approximation of one Markov chain by another
Jerrum M
Probab Theory Rel vol. 135 (1), 1-14.

DOI 10.1007/s00440-005-0453-4

01-05-2006

Systematic scan for sampling colorings
Dyer M, Goldberg LA and Jerrum M
Ann Appl Probab vol. 16 (1), 185-230.

DOI 10.1214/105051605000000683

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 scan
Dyer 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.

DOI 10.1007/11830924_31

01-01-2006

Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
Cryan M, Dyer M, Goldberg LA, Jerrum M and Martin R
Siam J Comput vol. 36 (1), 247-278.

DOI 10.1137/S0097539703434243

01-01-2006

Two remarks concerning balanced matroids
Jerrum M
Combinatorica vol. 26 (6), 733-742.

DOI 10.1007/s00493-006-0039-5

01-01-2006

Markov chain comparison
JERRUM MR, Martin R, Dyer M and Goldberg LA
Probability Surveys vol. 3, 89-111.

DOI 10.1214/154957806000000041

01-01-2006

2004

Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
Jerrum M, Son JB, Tetali P and Vigoda E
Ann Appl Probab vol. 14 (4), 1741-1765.

DOI 10.1214/105051604000000639

01-11-2004

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Jerrum M, Sinclair A and Vigoda E
J Acm vol. 51 (4), 671-697.

DOI 10.1145/1008731.1008738

01-07-2004

Special issue on Isaac Newton Institute Programme - Computation, combinatorics and probability: Part I - Preface
Dyer M, Jerrum M and Winkler P
Random Struct Algor vol. 24 (3), 233-233.

DOI 10.1002/rsa.20010

01-05-2004

The relative complexity of approximate counting problems
Dyer M, Goldberg LA, Greenhill C and Jerrum M
Algorithmica vol. 38 (3), 471-500.

DOI 10.1007/s00453-003-1073-y

01-03-2004

Counting and sampling H-colourings
Dyer M, Goldberg LA and Jerrum M
Inform Comput vol. 189 (1), 1-16.

DOI 10.1016/j.ic.2003.09.001

25-02-2004

A bound on the capacity of backoff and acknowledgment-based protocols
Goldberg LA, Jerrum M, Kannan S and Paterson M
Siam J Comput vol. 33 (2), 313-331.

DOI 10.1137/S0097539700381851

01-01-2004

2003

The computational complexity of two-state spin systems
Goldberg LA, Jerrum M and Paterson M
Random Struct Algor vol. 23 (2), 133-154.

DOI 10.1002/rsa.10090

01-09-2003

Counting, Sampling and Integrating: Algorithm and Complexity
Jerrum M

DOI 10.1007/978-3-0348-8005-3

01-01-2003

2002

On counting independent sets in sparse graphs
Dyer M, Frieze A and Jerrum M
SIAM JOURNAL ON COMPUTING. vol. 31 (5), 1527-1541.

DOI 10.1137/S0097539701383844

15-08-2002

Convergence of the iterated prisoner's dilemma game
Dyer M, Goldberg LA, Greenhill C, Istrate G and Jerrum M
Comb Probab Comput vol. 11 (2), 135-147.

DOI 10.1017/S096354830100503X

01-03-2002

The 'Burnside process' converges slowly
Goldberg LA and Jerrum M
Comb Probab Comput vol. 11 (1), 21-34.

DOI 10.1017/S096354830100493X

01-01-2002

Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
Cryan M, Dyer M, Goldberg LA, Jerrum M and Martin R
FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 711-720.

DOI 10.1109/SFCS.2002.1181996

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.

DOI 10.1007/3-540-45726-7_5

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.

DOI 10.1007/3-540-45726-7_6

01-01-2002

Spectral gap and log-Sobolev constant for balanced matroids
Jerrum M and Son JB
FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 721-729.

DOI 10.1109/SFCS.2002.1181997

01-01-2002

2001

An extension of path coupling and its application to the Glauber dynamics for graph colorings
Dyer M, Goldberg LA, Greenhill C, Jerrum M and Mitzenmacher M
Siam J Comput vol. 30 (6), 1962-1975.

DOI 10.1137/s0097539700372708

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.

DOI 10.1145/380752.380877

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 Molecules
Goldberg LA and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 29 (3), 834-853.

DOI 10.1137/s0097539797318864

01-01-2000

Counting Unlabelled Subtrees of a Tree is #P-complete
Goldberg LA and Jerrum M
Lms Journal of Computation and Mathematics, Wiley vol. 3, 117-124.

DOI 10.1112/s1461157000000243

01-01-2000

1999

The Swendsen–Wang Process Does Not Always Mix Rapidly
Gore VK and Jerrum MR
Journal of Statistical Physics, Springer Nature vol. 97 (1-2), 67-86.

DOI 10.1023/a:1004610900745

01-10-1999

On Approximately Counting Colorings of Small Degree Graphs
Bubley R, Dyer M, Greenhill C and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 29 (2), 387-400.

DOI 10.1137/s0097539798338175

01-01-1999

1998

Approximately Counting Hamilton Paths and Cycles in Dense Graphs
Dyer M, Frieze A and Jerrum M
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 27 (5), 1262-1272.

DOI 10.1137/s009753979426112x

01-10-1998

An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks
Goldberg LA, Jerrum M and MacKenzie PD
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 27 (4), 1083-1098.

DOI 10.1137/s0097539794272569

01-08-1998

An elementary analysis of a procedure for sampling points in a convex body
Bubley R, Dyer M and Jerrum M
Random Structures and Algorithms, Wiley vol. 12 (3), 213-235.

DOI 10.1002/(sici)1098-2418(199805)12:3<213::aid-rsa1>3.0.co;2-y

01-05-1998

The Metropolis algorithm for graph bisection
Jerrum M and Sorkin GB
Discrete Applied Mathematics, Elsevier vol. 82 (1-3), 155-175.

DOI 10.1016/s0166-218x(97)00133-9

01-03-1998

1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers
Goldberg LA, Jerrum M, Leighton T and Rao S
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 26 (4), 1100-1119.

DOI 10.1137/s0097539793259483

01-08-1997

Improved approximation algorithms for MAXk-CUT and MAX BISECTION
Frieze A and Jerrum M
Algorithmica, Springer Nature vol. 18 (1), 67-81.

DOI 10.1007/bf02523688

01-05-1997

1995

A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Jerrum M
Random Structures and Algorithms, Wiley vol. 7 (2), 157-165.

DOI 10.1002/rsa.3240070205

01-09-1995

1994

Simple Translation-Invariant Concepts Are Hard to Learn
Jerrum M
Information and Computation, Elsevier vol. 113 (2), 300-311.

DOI 10.1006/inco.1994.1074

01-09-1994

Counting trees in a graph is #P-complete
Jerrum M
Information Processing Letters, Elsevier vol. 51 (3), 111-116.

DOI 10.1016/0020-0190(94)00085-9

01-08-1994

Three-dimensional Statistical Data Security Problems
Irving RW and Jerrum MR
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 23 (1), 170-184.

DOI 10.1137/s0097539790191010

01-02-1994

1993

Polynomial-Time Approximation Algorithms for the Ising Model
Jerrum M and Sinclair A
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 22 (5), 1087-1116.

DOI 10.1137/0222066

01-10-1993

1992

Large Cliques Elude the Metropolis Process
Jerrum M
Random Structures and Algorithms, Wiley vol. 3 (4), 347-359.

DOI 10.1002/rsa.3240030402

01-01-1992

1990

Fast uniform generation of regular graphs
Jerrum M and Sinclair A
Theoretical Computer Science, Elsevier vol. 73 (1), 91-100.

DOI 10.1016/0304-3975(90)90164-d

01-06-1990

Two-dimensional monomer-dimer systems are computationally intractable
Jerrum M
Journal of Statistical Physics, Springer Nature vol. 59 (3-4), 1087-1088.

DOI 10.1007/bf01025864

01-05-1990

1989

Approximating the Permanent
Jerrum M and Sinclair A
Siam Journal On Computing, Society For Industrial & Applied Mathematics (Siam) vol. 18 (6), 1149-1178.

DOI 10.1137/0218077

01-12-1989

Approximate counting, uniform generation and rapidly mixing Markov chains
Sinclair A and Jerrum M
Information and Computation, Elsevier vol. 82 (1), 93-133.

DOI 10.1016/0890-5401(89)90067-9

01-07-1989

1987

Two-dimensional monomer-dimer systems are computationally intractable
Jerrum M
Journal of Statistical Physics, Springer Nature vol. 48 (1-2), 121-134.

DOI 10.1007/bf01010403

01-07-1987

1986

A compact representation for permutation groups
Jerrum M
Journal of Algorithms, Elsevier vol. 7 (1), 60-78.

DOI 10.1016/0196-6774(86)90038-6

01-03-1986

Random generation of combinatorial structures from a uniform distribution
Jerrum MR, Valiant LG and Vazirani VV
Theoretical Computer Science, Elsevier vol. 43, 169-188.

DOI 10.1016/0304-3975(86)90174-x

01-01-1986

1985

The complexity of finding minimum-length generator sequences
Jerrum MR
Theoretical Computer Science, Elsevier vol. 36, 265-289.

DOI 10.1016/0304-3975(85)90047-7

01-01-1985

1984

Families of Fixed Degree Graphs for Processor Interconnection
Jerrum MR and Skyum S
Ieee Transactions On Computers, Institute of Electrical and Electronics Engineers (Ieee) vol. C-33 (2), 190-194.

DOI 10.1109/tc.1984.1676410

01-02-1984

1982

Some Exact Complexity Results for Straight-Line Computations over Semirings
Jerrum M and Snir M
Journal of The Acm, Association For Computing Machinery (Acm) vol. 29 (3), 874-897.

DOI 10.1145/322326.322341

01-07-1982

Grants

Grants of specific relevance to the Centre for Combinatorics, Algebra and Number Theory

Maths Research Associates 2021
Mark Jerrum
£400,000 EPSRC Engineering and Physical Sciences Research Council
01-01-2021 - 30-09-2023

Sampling in Hereditary Classes - lead site University of Leeds
Mark Jerrum
£78,310 EPSRC Engineering and Physical Sciences Research Council
01-04-2019 - 31-07-2023

Algorithms That Count
Mark Jerrum
£361,972 EPSRC Engineering and Physical Sciences Research Council
01-11-2015 - 30-04-2019