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
Jerrum M (2024). Fundamentals of Partial Rejection Sampling. Probability Surveys, Institute of Mathematical Statistics 03-09-2024
Anand K and Jerrum M (2024). Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixing. Annales de l’Institut Henri Poincaré D Combinatorics Physics and their Interactions, European Mathematical Society - EMS - Publishing House 02-08-2024
2023
Jerrum M, Guo H, Wang J and Feng W (2023). A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. TheoretiCS, EPIsciences 15-06-2023
2022
Anand K and Jerrum M (2022). Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 51 (4), 1280-1295. 26-07-2022
Guo H and Jerrum M (2022). Counting vertices of integral polytopes defined by facets. Discrete and Computational Geometry, Springer 05-07-2022
2021
Jerrum M, Dyer M, Müller H and Vušković K (2021). Counting weighted independent sets beyond the permanent. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics vol. 35 (2), 1503-1524. 24-06-2021
Jerrum M, Dyer M, Heinrich M and Müller H (2021). Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. Combinatorics, Probability and Computing, Cambridge University Press (CUP) 12-04-2021
Jerrum M and Makai T (2021). The Size of the Giant Joint Component in a Binomial Random Double Graph. The Electronic Journal of Combinatorics vol. 28 (1) 12-02-2021
Jerrum MR (2021). Sharp thresholds of graph properties, and the k-sat problem. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY vol. 58 (2), 267-268. 01-01-2021
2020
Jerrum M, Galanis A, Goldberg LA, Vigoda E and Dyer M (2020). Random Walks on Small World Networks. ACM Transactions on Algorithms, Association for Computing Machinery vol. 16 (3) 01-06-2020
2019
Jerrum M and Goldberg LA (2019). Approximating Pairwise Correlations in the Ising Model. ACM Transactions on Computation Theory, Association for Computing Machinery vol. 11 (4) 01-07-2019
Guo H and Jerrum M (2019). A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 48 (3), 964-978. 09-05-2019
Guo H, Jerrum M and Liu J (2019). Uniform Sampling Through the Lovász Local Lemma. Journal of the ACM, Association for Computing Machinery (ACM) vol. 66 (3), 1-31. 12-04-2019
2018
Guo H and Jerrum M (2018). Perfect simulation of the hard disks model by partial rejection sampling. 01-07-2018
Guo H and Jerrum M (2018). A polynomial-time approximation algorithm for all-terminal network reliability. 01-07-2018
Guo H and JERRUM MR (2018). Random cluster dynamics for the Ising model is rapidly mixing. Annals of Applied Probability, Institute of Mathematical Statistics 11-04-2018
2017
Jerrum M and Meeks K (2017). The parameterised complexity of counting even and odd induced subgraphs. COMBINATORICA vol. 37 (5), 965-990. 01-10-2017
Guo H, Jerrum M and Liu J (2017). Uniform sampling through the Lovász Local Lemma. STOC’17, Montreal, Canada. 19-06-2017
Dyer M, JERRUM MR and Müller H (2017). On the switch Markov chain for perfect matchings. Journal of the Association for Computing Machinery (ACM), Association for Computing Machinery vol. 64 (2) 12-05-2017
Bulatov A, Goldberg LA, Jerrum M, Richerby D and Živný S (2017). Functional clones and expressibility of partition functions. Theoretical Computer Science 11-05-2017
JERRUM MR, Galanis A and Goldberg LA (2017). A complexity trichotomy for approximately counting list H-colourings. ACM Transactions on Computation Theory, Association for Computing Maachinery vol. 9 (2) 01-05-2017
Jerrum M (2017). Counting Constraint Satisfaction Problems. The Constraint Satisfaction Problem , Editors: Krokhin AA and Zivný S. 205-231. 01-01-2017
2016
Galanis A, Goldberg LA and Jerrum M (2016). A complexity trichotomy for approximately counting list H-colourings. 01-08-2016
Goldberg LA and Jerrum M (2016). The complexity of counting locally maximal satisfying assignments of Boolean CSPs. Theoretical Computer Science, Elsevier vol. 634, 35-46. 01-06-2016
Galanis A, Goldberg LA and Jerrum M (2016). APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD. SIAM JOURNAL ON COMPUTING vol. 45 (3), 680-711. 19-05-2016
2015
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D and Vigoda E (2015). #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences vol. 82 (5), 690-711. 02-12-2015
Goldberg LA and Jerrum M (2015). A complexity classification of spin systems with an external field. Proceedings of the National Academy of Sciences of the United States of America vol. 112 (43), 13161-13166. 01-10-2015
Jerrum M and Meeks K (2015). Some Hard Families of Parameterized Counting Problems. ACM Transactions on Computation Theory, Association for Computing Machinery (ACM) vol. 7 (3), 1-18. 09-07-2015
Faben J and Jerrum M (2015). The complexity of parity graph homomorphism: An initial investigation. Theory of Computing vol. 11, 35-57. 14-03-2015
Chen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D (2015). The complexity of approximating conservative counting CSPs. Journal of Computer and System Sciences vol. 81 (1), 311-329. 01-02-2015
Galanis A, Goldberg LA and Jerrum M (2015). Approximately Counting H-Colourings is #BIS-Hard. 01-01-2015
Galanis A, Goldberg LA and Jerrum M (2015). Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard., Editors: Halldórsson MM, Iwama K, Kobayashi N and Speckmann B. 01-01-2015
Goldberg LA, Jerrum M and McQuillan C (2015). Approximating the partition function of planar two-state spin systems. J. Comput. Syst. Sci. vol. 81, 330-358. 01-01-2015
2014
Jerrum M and Meeks K (2014). The parameterised complexity of counting connected subgraphs and graph motifs. JOURNAL OF COMPUTER AND SYSTEM SCIENCES vol. 81 (4), 702-716. 24-11-2014
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D and Vigoda E (2014). BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. 01-09-2014
Goldberg LA and Jerrum M (2014). The Complexity of Approximately Counting Tree Homomorphisms. ACM Transactions on Computation Theory, Association for Computing Machinery (ACM) vol. 6 (2), 1-31. 01-05-2014
Goldberg LA and Jerrum M (2014). The Complexity of Computing the Sign of the Tutte Polynomial. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 43 (6), 1921-1952. 01-01-2014
2013
Bulatov A, Dyer M, Goldberg LA, Jerrum M and McQuillan C (2013). The expressibility of functions on the Boolean domain, with applications to Counting CSPs. J. Assoc. Comput. Mach., ACM Digital Library vol. 60 (5) 01-10-2013
Goldberg LA and Jerrum M (2013). Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. JOURNAL OF COMPUTER AND SYSTEM SCIENCES vol. 79 (1), 68-78. 01-01-2013
Goldberg LA and Jerrum M (2013). A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. SIAM J. Comput. vol. 42, 1132-1157. 01-01-2013
Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D (2013). The complexity of approximating conservative counting CSPs., Editors: Portier N and Wilke T. 01-01-2013
2012
Goldberg LA and Jerrum M (2012). A counterexample to rapid mixing of the Ge-Stefankovic process. ELECTRONIC COMMUNICATIONS IN PROBABILITY vol. 17, 1-6. 01-01-2012
Bulatov A, Dyer M, Goldberg LA, Jalsenius M, Jerrum M and Richerby D (2012). The complexity of weighted and unweighted #CSP. JOURNAL OF COMPUTER AND SYSTEM SCIENCES vol. 78 (2), 681-688. 01-01-2012
Goldberg LA and Jerrum M (2012). Inapproximability of the Tutte polynomial of a planar graph. COMPUTATIONAL COMPLEXITY vol. 21 (4), 605-642. 01-01-2012
Goldberg LA and Jerrum M (2012). Approximating the Partition Function of the Ferromagnetic Potts Model. JOURNAL OF THE ACM vol. 59 (5) 01-01-2012
Goldberg LA, Jerrum M and McQuillan C (2012). Approximating the partition function of planar two-state spin systems. CoRR vol. abs/1208.4987 01-01-2012
Bulatov AA, Dyer ME, Goldberg LA and Jerrum M (2012). Log-supermodular functions, functional clones and counting CSPs., Editors: Dürr C and Wilke T. 01-01-2012
Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C and Richerby D (2012). The complexity of approximating conservative counting CSPs. CoRR vol. abs/1208.1783 01-01-2012
Goldberg LA and Jerrum M (2012). The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)., Editors: Czumaj A, Mehlhorn K, Pitts AM and Wattenhofer R. 01-01-2012
2011
Goldberg LA and Jerrum M (2011). A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid., Editors: Aceto L, Henzinger M and Sgall J. 01-01-2011
2010
Dyer M, Goldberg LA and Jerrum M (2010). A Complexity Dichotomy For Hypergraph Partition Functions. COMPUT COMPLEX vol. 19 (4), 605-633. 01-12-2010
Jerrum M (2010). Technical Perspective Constraint Satisfaction Problems and Computational Complexity. COMMUN ACM vol. 53 (9), 98-98. 01-09-2010
Goldberg LA, Jerrum M and Karpinski M (2010). The Mixing Time of Glauber Dynamics for Coloring Regular Trees. RANDOM STRUCT ALGOR vol. 36 (4), 464-476. 01-07-2010
Dyer M, Goldberg LA and Jerrum M (2010). An approximation trichotomy for Boolean #CSP. J COMPUT SYST SCI vol. 76 (3-4), 267-277. 01-05-2010
Goldberg LA and Jerrum M (2010). Approximating the Partition Function of the Ferromagnetic Potts Model., Editors: Abramsky S, Gavoille C, Kirchner C, MeyerAufDerHeide F and Spirakis PG. 01-01-2010
Goldberg LA and Jerrum M (2010). Approximating the Partition Function of the Ferromagnetic Potts Model., Editors: Abramsky S, Gavoille C, Kirchner C, Heide FMAD and Spirakis PG. 01-01-2010
Goldberg LA, Grohe M, Jerrum M and Thurley M (2010). A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH MIXED SIGNS. SIAM J COMPUT vol. 39 (7), 3336-3402. 01-01-2010
2009
Dyer M, Goldberg LA and Jerrum M (2009). MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS. ANN APPL PROBAB vol. 19 (1), 71-107. 01-02-2009
Goldberg LA, Grohe M, Jerrum M and Thurley M (2009). A Complexity Dichotomy for Partition Functions with Mixed Signs., Editors: Albers S and Marion J-Y. 01-01-2009
2008
Dyer M, Goldberg LA and Jerrum M (2008). Dobrushin Conditions and Systematic Scan. COMB PROBAB COMPUT vol. 17 (6), 761-779. 01-11-2008
Goldberg LA and Jerrum M (2008). Inapproximability of the Tutte polynomial. INFORM COMPUT vol. 206 (7), 908-929. 01-07-2008
Dyer M, Goldberg LA and Jerrum M (2008). THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP. SIAM J COMPUT vol. 38 (5), 1970-1986. 01-01-2008
2007
Goldberg LA and Jerrum M (2007). Inapproximability of the Tutte polynomial., Editors: Johnson DS and Feige U. 01-01-2007
Goldberg LA and Jerrum M (2007). The complexity of ferromagnetic ising with local fields. COMB PROBAB COMPUT vol. 16 (1), 43-61. 01-01-2007
2006
Jerrum M (2006). On the approximation of one Markov chain by another. PROBAB THEORY REL vol. 135 (1), 1-14. 01-05-2006
Dyer M, Goldberg LA and Jerrum M (2006). Systematic scan for sampling colorings. ANN APPL PROBAB vol. 16 (1), 185-230. 01-02-2006
Dyer ME, Goldberg LA and Jerrum M (2006). Dobrushin Conditions and Systematic Scan., Editors: Díaz J, Jansen K, Rolim JDP and Zwick U. 01-01-2006
Dyer M, Goldberg LA and Jerrum M (2006). Dobrushin conditions and systematic scan., Editors: Draz J, Jansen K, Rolim JDP and Zwick U. 01-01-2006
Cryan M, Dyer M, Goldberg LA, Jerrum M and Martin R (2006). Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. SIAM J COMPUT vol. 36 (1), 247-278. 01-01-2006
Jerrum M (2006). Two remarks concerning balanced matroids. COMBINATORICA vol. 26 (6), 733-742. 01-01-2006
JERRUM MR, Martin R, Dyer M and Goldberg LA (2006). Markov chain comparison. Probability Surveys vol. 3, 89-111. 01-01-2006
2004
Jerrum M, Son JB, Tetali P and Vigoda E (2004). Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains. ANN APPL PROBAB vol. 14 (4), 1741-1765. 01-11-2004
Jerrum M, Sinclair A and Vigoda E (2004). A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J ACM vol. 51 (4), 671-697. 01-07-2004
Dyer M, Jerrum M and Winkler P (2004). Special issue on Isaac Newton Institute Programme - Computation, combinatorics and probability: Part I - Preface. RANDOM STRUCT ALGOR vol. 24 (3), 233-233. 01-05-2004
Dyer M, Goldberg LA, Greenhill C and Jerrum M (2004). The relative complexity of approximate counting problems. ALGORITHMICA vol. 38 (3), 471-500. 01-03-2004
Dyer M, Goldberg LA and Jerrum M (2004). Counting and sampling H-colourings. INFORM COMPUT vol. 189 (1), 1-16. 25-02-2004
Goldberg LA, Jerrum M, Kannan S and Paterson M (2004). A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J COMPUT vol. 33 (2), 313-331. 01-01-2004
2003
Goldberg LA, Jerrum M and Paterson M (2003). The computational complexity of two-state spin systems. RANDOM STRUCT ALGOR vol. 23 (2), 133-154. 01-09-2003
2002
Dyer M, Goldberg LA, Greenhill C, Istrate G and Jerrum M (2002). Convergence of the iterated prisoner's dilemma game. COMB PROBAB COMPUT vol. 11 (2), 135-147. 01-03-2002
Goldberg LA and Jerrum M (2002). The 'Burnside process' converges slowly. COMB PROBAB COMPUT vol. 11 (1), 21-34. 01-01-2002
Cryan M, Dyer M, Goldberg LA, Jerrum M and Martin R (2002). Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. 01-01-2002
Dyer ME, Goldberg LA and Jerrum M (2002). Counting and Sampling H-Colourings., Editors: Rolim JDP and Vadhan SP. 01-01-2002
Dyer ME, Jerrum M and Vigoda E (2002). Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs., Editors: Rolim JDP and Vadhan SP. 01-01-2002
2001
Dyer M, Goldberg LA, Greenhill C, Jerrum M and Mitzenmacher M (2001). An extension of path coupling and its application to the Glauber dynamics for graph colorings. SIAM J COMPUT vol. 30 (6), 1962-1975. 01-01-2001
Jerrum M, Sinclair A and Vigoda E (2001). A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries., Editors: Vitter JS, Spirakis PG and Yannakakis M. 01-01-2001
Dyer ME, Jerrum M and Vigoda E (2001). Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs., Editors: Nesetril J and Winkler P. 01-01-2001
2000
Goldberg LA and Jerrum M (2000). Randomly Sampling Molecules. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 29 (3), 834-853. 01-01-2000
Goldberg LA and Jerrum M (2000). Counting Unlabelled Subtrees of a Tree is #P-complete. LMS Journal of Computation and Mathematics, Wiley vol. 3, 117-124. 01-01-2000
1999
Gore VK and Jerrum MR (1999). The Swendsen–Wang Process Does Not Always Mix Rapidly. Journal of Statistical Physics, Springer Nature vol. 97 (1-2), 67-86. 01-10-1999
Bubley R, Dyer M, Greenhill C and Jerrum M (1999). On Approximately Counting Colorings of Small Degree Graphs. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 29 (2), 387-400. 01-01-1999
1998
Dyer M, Frieze A and Jerrum M (1998). Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 27 (5), 1262-1272. 01-10-1998
Goldberg LA, Jerrum M and MacKenzie PD (1998). An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 27 (4), 1083-1098. 01-08-1998
Bubley R, Dyer M and Jerrum M (1998). An elementary analysis of a procedure for sampling points in a convex body. Random Structures and Algorithms, Wiley vol. 12 (3), 213-235. 01-05-1998
Jerrum M and Sorkin GB (1998). The Metropolis algorithm for graph bisection. Discrete Applied Mathematics, Elsevier vol. 82 (1-3), 155-175. 01-03-1998
1997
Goldberg LA, Jerrum M, Leighton T and Rao S (1997). Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 26 (4), 1100-1119. 01-08-1997
Frieze A and Jerrum M (1997). Improved approximation algorithms for MAXk-CUT and MAX BISECTION. Algorithmica, Springer Nature vol. 18 (1), 67-81. 01-05-1997
1995
Jerrum M (1995). A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph. Random Structures and Algorithms, Wiley vol. 7 (2), 157-165. 01-09-1995
1994
Jerrum M (1994). Simple Translation-Invariant Concepts Are Hard to Learn. Information and Computation, Elsevier vol. 113 (2), 300-311. 01-09-1994
Jerrum M (1994). Counting trees in a graph is #P-complete. Information Processing Letters, Elsevier vol. 51 (3), 111-116. 01-08-1994
Irving RW and Jerrum MR (1994). Three-dimensional Statistical Data Security Problems. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 23 (1), 170-184. 01-02-1994
1993
Jerrum M and Sinclair A (1993). Polynomial-Time Approximation Algorithms for the Ising Model. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 22 (5), 1087-1116. 01-10-1993
1992
Jerrum M (1992). Large Cliques Elude the Metropolis Process. Random Structures and Algorithms, Wiley vol. 3 (4), 347-359. 01-01-1992
1990
Jerrum M and Sinclair A (1990). Fast uniform generation of regular graphs. Theoretical Computer Science, Elsevier vol. 73 (1), 91-100. 01-06-1990
Jerrum M (1990). Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics, Springer Nature vol. 59 (3-4), 1087-1088. 01-05-1990
1989
Jerrum M and Sinclair A (1989). Approximating the Permanent. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 18 (6), 1149-1178. 01-12-1989
Sinclair A and Jerrum M (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, Elsevier vol. 82 (1), 93-133. 01-07-1989
1987
Jerrum M (1987). Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics, Springer Nature vol. 48 (1-2), 121-134. 01-07-1987
1986
Jerrum M (1986). A compact representation for permutation groups. Journal of Algorithms, Elsevier vol. 7 (1), 60-78. 01-03-1986
Jerrum MR, Valiant LG and Vazirani VV (1986). Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, Elsevier vol. 43, 169-188. 01-01-1986
1985
Jerrum MR (1985). The complexity of finding minimum-length generator sequences. Theoretical Computer Science, Elsevier vol. 36, 265-289. 01-01-1985
1984
Jerrum MR and Skyum S (1984). Families of Fixed Degree Graphs for Processor Interconnection. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers (IEEE) vol. C-33 (2), 190-194. 01-02-1984
1982
Jerrum M and Snir M (1982). Some Exact Complexity Results for Straight-Line Computations over Semirings. 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)