Professor Mark JerrumProfessor of MathematicsEmail: m.jerrum@qmul.ac.ukTelephone: +44 (0)20 7882 5472Room Number: Mathematical Sciences Building, Room: MB-511Website: http://www.maths.qmul.ac.uk/~mj/ProfileTeachingResearchPublicationsGrantsProfileMark Jerrum’s research interests lie in 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, he works on the computational complexity of counting problems, including weighted counting problems, as exemplified by partition functions and generating functions. Statistical physics, constraint satisfaction and graph polynomials provide a rich source of motivating examples. He is Director of Research in the School of Mathematical Sciences and is module organiser for MTH6140 Linear Algebra II. He serves on the editorial boards of SIAM Journal on Computing and Random Structures and Algorithms. Undergraduate TeachingMTH 5104, Convergence and ContinuityResearchExamples of research funding:EPSRC research grant Sampling in Hereditary Classes, EP/S016694/1. Start date 01/01/19, end date 31/12/21. £78K.Publications Guo H, Jerrum M (2022). Counting vertices of integral polytopes defined by facets Discrete and Computational Geometry nameOfConference. 10.1007/s00454-022-00406-8 https://qmro.qmul.ac.uk/xmlui/handle/123456789/78730 Anand K, Jerrum M (2022). PERFECT SAMPLING IN INFINITE SPIN SYSTEMS VIA STRONG SPATIAL MIXING SIAM Journal on Computing nameOfConference. 10.1137/21M1437433 https://qmro.qmul.ac.uk/xmlui/handle/123456789/78734 Jerrum M, Dyer M, Müller H et al. (2021). Counting weighted independent sets beyond the permanent SIAM Journal on Discrete Mathematics nameOfConference. 10.1137/20M1347747 https://qmro.qmul.ac.uk/xmlui/handle/123456789/72824 Jerrum M, Dyer M, Heinrich M et al. (2021). Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs Combinatorics, Probability and Computing nameOfConference. 10.1017/S0963548321000080 https://qmro.qmul.ac.uk/xmlui/handle/123456789/71189 Jerrum MR (2021). Sharp thresholds of graph properties, and the k-sat problem BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY nameOfConference. doi qmroHref Jerrum M, Makai T (2021). The Size of the Giant Joint Component in a Binomial Random Double Graph The Electronic Journal of Combinatorics nameOfConference. 10.37236/8846 https://qmro.qmul.ac.uk/xmlui/handle/123456789/70502 Jerrum M, Galanis A, Goldberg LA et al. (2020). Random Walks on Small World Networks ACM Transactions on Algorithms nameOfConference. 10.1145/3403658 https://qmro.qmul.ac.uk/xmlui/handle/123456789/63144 Jerrum M, Goldberg LA (2019). Approximating Pairwise Correlations in the Ising Model ACM Transactions on Computation Theory nameOfConference. 10.1145/3337785 https://qmro.qmul.ac.uk/xmlui/handle/123456789/57925 Guo H, Jerrum M (2019). A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability SIAM Journal on Computing nameOfConference. 10.1137/18m1201846 https://qmro.qmul.ac.uk/xmlui/handle/123456789/57919 Guo H, Jerrum M, Liu J (2019). Uniform sampling through the Lovász local lemma Journal of the ACM nameOfConference. 10.1145/3310131 https://qmro.qmul.ac.uk/xmlui/handle/123456789/56791 Guo H, JERRUM MR (2018). Random cluster dynamics for the Ising model is rapidly mixing Annals of Applied Probability nameOfConference. 10.1214/17-aap1335 https://qmro.qmul.ac.uk/xmlui/handle/123456789/28347 Guo H, Jerrum M (2018). A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. ICALP nameOfConference. doi qmroHref Guo H, Jerrum M (2018). Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. ICALP nameOfConference. doi qmroHref Jerrum M, Meeks K (2017). The parameterised complexity of counting even and odd induced subgraphs COMBINATORICA nameOfConference. 10.1007/s00493-016-3338-5 https://qmro.qmul.ac.uk/xmlui/handle/123456789/18110 Guo H, Jerrum M, Liu J (2017). Uniform sampling through the Lovász Local Lemma Proceedings of the Annual ACM Symposium on Theory of Computing STOC’17, Montreal, Canada. 10.1145/3055399.3055410 https://qmro.qmul.ac.uk/xmlui/handle/123456789/25213 Dyer M, JERRUM MR, Müller H (2017). On the switch Markov chain for perfect matchings Journal of the Association for Computing Machinery (ACM) nameOfConference. 10.1145/2822322 https://qmro.qmul.ac.uk/xmlui/handle/123456789/22454 Bulatov A, Goldberg LA, Jerrum M et al. (2017). Functional clones and expressibility of partition functions Theoretical Computer Science nameOfConference. 10.1016/j.tcs.2017.05.001 https://qmro.qmul.ac.uk/xmlui/handle/123456789/23690 JERRUM MR, Galanis A, Goldberg LA (publicationYear). A complexity trichotomy for approximately counting list H-colourings ACM Transactions on Computation Theory nameOfConference. 10.1145/3037381 https://qmro.qmul.ac.uk/xmlui/handle/123456789/22421 Jerrum M (2017). Counting Constraint Satisfaction Problems. journal nameOfConference. doi qmroHref Goldberg LA, Jerrum M (2016). The complexity of counting locally maximal satisfying assignments of Boolean CSPs Theoretical Computer Science nameOfConference. 10.1016/j.tcs.2016.04.008 https://qmro.qmul.ac.uk/xmlui/handle/123456789/12631 Galanis A, Goldberg LA, Jerrum M (2016). APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD SIAM JOURNAL ON COMPUTING nameOfConference. 10.1137/15M1020551 https://qmro.qmul.ac.uk/xmlui/handle/123456789/13055 Galanis A, Goldberg LA, Jerrum M (2016). A Complexity Trichotomy for Approximately Counting List H-Colourings. ICALP nameOfConference. doi qmroHref Cai JY, Galanis A, Goldberg LA et al. (2016). #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region Journal of Computer and System Sciences nameOfConference. 10.1016/j.jcss.2015.11.009 https://qmro.qmul.ac.uk/xmlui/handle/123456789/12757 Goldberg LA, 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 nameOfConference. 10.1073/pnas.1505664112 qmroHref Jerrum M, Meeks K (2015). Some Hard Families of Parameterized Counting Problems ACM Transactions on Computation Theory nameOfConference. 10.1145/2786017 qmroHref Galanis A, Goldberg LA, Jerrum M (2015). Approximately Counting H-Colourings is #BIS-Hard journal nameOfConference. 10.1007/978-3-662-47672-7_43 qmroHref Chen X, Dyer M, Goldberg LA et al. (2015). The complexity of approximating conservative counting CSPs Journal of Computer and System Sciences nameOfConference. 10.1016/j.jcss.2014.06.006 https://qmro.qmul.ac.uk/xmlui/handle/123456789/30088 Faben J, Jerrum M (publicationYear). title Theory of Computing nameOfConference. 10.4086/toc.2015.v011a002 qmroHref Galanis A, Goldberg LA, Jerrum M (2015). Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. ICALP (1) nameOfConference. doi qmroHref Goldberg LA, Jerrum M, McQuillan C (2015). Approximating the partition function of planar two-state spin systems. J. Comput. Syst. Sci. nameOfConference. 10.1016/j.jcss.2014.06.007 qmroHref Jerrum M, Meeks K (2014). The parameterised complexity of counting connected subgraphs and graph motifs JOURNAL OF COMPUTER AND SYSTEM SCIENCES nameOfConference. 10.1016/j.jcss.2014.11.015 https://qmro.qmul.ac.uk/xmlui/handle/123456789/18887 Cai JY, Galanis A, Goldberg LA et al. (2014). BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region Leibniz International Proceedings in Informatics, LIPIcs nameOfConference. 10.4230/LIPIcs.APPROX-RANDOM.2014.582 qmroHref Goldberg LA, Jerrum M (2014). The Complexity of Approximately Counting Tree Homomorphisms ACM Transactions on Computation Theory nameOfConference. 10.1145/2600917 qmroHref Goldberg LA, Jerrum M (2014). The Complexity of Computing the Sign of the Tutte Polynomial SIAM Journal on Computing nameOfConference. 10.1137/12088330x https://qmro.qmul.ac.uk/xmlui/handle/123456789/7564 Bulatov A, Dyer M, Goldberg LA et al. (2013). The expressibility of functions on the Boolean domain, with applications to Counting CSPs J. Assoc. Comput. Mach. nameOfConference. 10.1145/2528401 https://qmro.qmul.ac.uk/xmlui/handle/123456789/10337 Goldberg LA, Jerrum M (2013). Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials JOURNAL OF COMPUTER AND SYSTEM SCIENCES nameOfConference. 10.1016/j.jcss.2012.04.005 qmroHref Goldberg LA, Jerrum M (2013). A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. SIAM J. Comput. nameOfConference. 10.1137/110851213 qmroHref Chen X, Dyer ME, Goldberg LA et al. (2013). The complexity of approximating conservative counting CSPs. STACS nameOfConference. doi qmroHref Goldberg LA, Jerrum M (2012). Inapproximability of the Tutte polynomial of a planar graph COMPUTATIONAL COMPLEXITY nameOfConference. 10.1007/s00037-012-0046-4 qmroHref Goldberg LA, Jerrum M (2012). Approximating the Partition Function of the Ferromagnetic Potts Model JOURNAL OF THE ACM nameOfConference. 10.1145/2371656.2371660 qmroHref Bulatov A, Dyer M, Goldberg LA et al. (2012). The complexity of weighted and unweighted #CSP JOURNAL OF COMPUTER AND SYSTEM SCIENCES nameOfConference. 10.1016/j.jcss.2011.12.002 qmroHref Goldberg LA, Jerrum M (2012). A counterexample to rapid mixing of the Ge-Stefankovic process ELECTRONIC COMMUNICATIONS IN PROBABILITY nameOfConference. 10.1214/ECP.v17-1712 qmroHref Goldberg LA, Jerrum M, McQuillan C (2012). Approximating the partition function of planar two-state spin systems CoRR nameOfConference. 10.1016/j.jcss.2014.06.007 qmroHref Bulatov AA, Dyer ME, Goldberg LA et al. (2012). Log-supermodular functions, functional clones and counting CSPs. STACS nameOfConference. doi qmroHref Goldberg LA, Jerrum M (2012). The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). ICALP (1) nameOfConference. doi qmroHref Chen X, Dyer ME, Goldberg LA et al. (2012). The complexity of approximating conservative counting CSPs CoRR nameOfConference. 10.4230/LIPIcs.STACS.2013.148 qmroHref Goldberg LA, Jerrum M (2011). A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. ICALP (1) nameOfConference. doi qmroHref Dyer M, Goldberg LA, Jerrum M (2010). A Complexity Dichotomy For Hypergraph Partition Functions COMPUT COMPLEX nameOfConference. 10.1007/s00037-010-0300-6 qmroHref Jerrum M (2010). Technical Perspective Constraint Satisfaction Problems and Computational Complexity COMMUN ACM nameOfConference. 10.1145/1810891.1810913 qmroHref Goldberg LA, Jerrum M, Karpinski M (2010). The Mixing Time of Glauber Dynamics for Coloring Regular Trees RANDOM STRUCT ALGOR nameOfConference. 10.1002/rsa.20303 qmroHref Dyer M, Goldberg LA, Jerrum M (2010). An approximation trichotomy for Boolean #CSP J COMPUT SYST SCI nameOfConference. 10.1016/j.jcss.2009.08.003 qmroHref Goldberg LA, Grohe M, Jerrum M et al. (2010). A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH MIXED SIGNS SIAM J COMPUT nameOfConference. 10.1137/090757496 qmroHref Goldberg LA, Jerrum M (2010). Approximating the Partition Function of the Ferromagnetic Potts Model AUTOMATA, LANGUAGES AND PROGRAMMING, PT I nameOfConference. 10.1007/978-3-642-14165-2_34 qmroHref Goldberg LA, Jerrum M (2010). Approximating the Partition Function of the Ferromagnetic Potts Model. ICALP (1) nameOfConference. doi qmroHref Dyer M, Goldberg LA, Jerrum M (2009). MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS ANN APPL PROBAB nameOfConference. 10.1214/08-AAP532 qmroHref Goldberg LA, Grohe M, Jerrum M et al. (2009). A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS nameOfConference. doi qmroHref Dyer M, Goldberg LA, Jerrum M (2008). Dobrushin Conditions and Systematic Scan COMB PROBAB COMPUT nameOfConference. 10.1017/S0963548308009437 qmroHref Goldberg LA, Jerrum M (2008). Inapproximability of the Tutte polynomial INFORM COMPUT nameOfConference. 10.1016/j.ic.2008.04.003 qmroHref Dyer M, Goldberg LA, Jerrum M (2008). THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP SIAM J COMPUT nameOfConference. 10.1137/070690201 qmroHref Goldberg LA, Jerrum M (2007). Inapproximability of the Tutte Polynomial STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING nameOfConference. 10.1145/1250790.1250858 qmroHref Goldberg LA, Jerrum M (2007). Inapproximability of the Tutte polynomial. STOC nameOfConference. doi qmroHref Goldberg LA, Jerrum M (2007). The complexity of ferromagnetic ising with local fields COMB PROBAB COMPUT nameOfConference. 10.1017/S096354830600767X qmroHref Jerrum M (2006). On the approximation of one Markov chain by another PROBAB THEORY REL nameOfConference. 10.1007/s00440-005-0453-4 qmroHref Dyer M, Goldberg LA, Jerrum M (2006). Systematic scan for sampling colorings ANN APPL PROBAB nameOfConference. 10.1214/105051605000000683 qmroHref Dyer ME, Goldberg LA, Jerrum M (2006). Dobrushin Conditions and Systematic Scan. APPROX-RANDOM nameOfConference. doi qmroHref Dyer M, Goldberg LA, Jerrum M (2006). Dobrushin conditions and systematic scan APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES nameOfConference. 10.1007/11830924_31 qmroHref JERRUM MR, Martin R, Dyer M et al. (2006). Markov chain comparison Probability Surveys nameOfConference. 10.1214/154957806000000041 qmroHref Cryan M, Dyer M, Goldberg LA et al. (2006). Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows SIAM J COMPUT nameOfConference. 10.1137/S0097539703434243 qmroHref Jerrum M (2006). Two remarks concerning balanced matroids COMBINATORICA nameOfConference. 10.1007/s00493-006-0039-5 qmroHref Jerrum M, Son JB, Tetali P et al. (2004). Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains ANN APPL PROBAB nameOfConference. 10.1214/105051604000000639 qmroHref Jerrum M, Sinclair A, Vigoda E (2004). A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries J ACM nameOfConference. 10.1145/1008731.1008738 qmroHref Dyer M, Jerrum M, Winkler P (2004). Special issue on Isaac Newton Institute Programme - "Computation, combinatorics and probability": Part I - Preface RANDOM STRUCT ALGOR nameOfConference. 10.1002/rsa.20010 qmroHref Dyer M, Goldberg LA, Greenhill C et al. (2004). The relative complexity of approximate counting problems ALGORITHMICA nameOfConference. 10.1007/s00453-003-1073-y qmroHref Dyer M, Goldberg LA, Jerrum M (2004). Counting and sampling H-colourings INFORM COMPUT nameOfConference. 10.1016/j.ic.2003.09.001 qmroHref Goldberg LA, Jerrum M, Kannan S et al. (2004). A bound on the capacity of backoff and acknowledgment-based protocols SIAM J COMPUT nameOfConference. 10.1137/S0097539700381851 qmroHref Goldberg LA, Jerrum M, Paterson M (2003). The computational complexity of two-state spin systems RANDOM STRUCT ALGOR nameOfConference. 10.1002/rsa.10090 qmroHref Jerrum M (2003). Counting, Sampling and Integrating: Algorithm and Complexity journal nameOfConference. 10.1007/978-3-0348-8005-3 qmroHref Dyer M, Frieze A, Jerrum M (2002). On counting independent sets in sparse graphs SIAM JOURNAL ON COMPUTING nameOfConference. 10.1137/S0097539701383844 qmroHref Dyer M, Goldberg LA, Greenhill C et al. (2002). Convergence of the iterated prisoner's dilemma game COMB PROBAB COMPUT nameOfConference. 10.1017/S096354830100503X qmroHref Dyer ME, Goldberg LA, Jerrum M (2002). Counting and Sampling H-Colourings. RANDOM nameOfConference. 10.1007/3-540-45726-7_5 qmroHref Dyer ME, Jerrum M, Vigoda E (2002). Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. RANDOM nameOfConference. 10.1007/3-540-45726-7_6 qmroHref Cryan M, Dyer M, Goldberg LA et al. (2002). Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS nameOfConference. 10.1109/SFCS.2002.1181996 qmroHref Jerrum M, Son JB (2002). Spectral gap and log-Sobolev constant for balanced matroids FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS nameOfConference. 10.1109/SFCS.2002.1181997 qmroHref Goldberg LA, Jerrum M (2002). The 'Burnside process' converges slowly COMB PROBAB COMPUT nameOfConference. 10.1017/S096354830100493X qmroHref Jerrum M, Sinclair A, Vigoda E (2001). A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC nameOfConference. 10.1145/380752.380877 qmroHref Dyer M, Goldberg LA, Greenhill C et al. (2001). An extension of path coupling and its application to the Glauber dynamics for graph colorings SIAM J COMPUT nameOfConference. 10.1137/s0097539700372708 qmroHref Dyer ME, Jerrum M, Vigoda E (2001). Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. Graphs, Morphisms and Statistical Physics nameOfConference. doi qmroHref Grants EP/N004221/1 Algorithms that count: exploring the limits of tractability