Skip to main content
Research
  1. Queen Mary University of London
  2. Research
  3. Publications

Publications: Prof Mark Jerrum

Back to Search
Jerrum M ( 2024 ) . Fundamentals of Partial Rejection Sampling . Probability Surveys
Anand K, Jerrum M ( 2024 ) . Perfect sampling of $q$-spin systems on $\mathbb{Z}^{2}$ via weak spatial mixing . Annales de l’Institut Henri Poincaré D
Jerrum M, Guo H, Wang J, Feng W ( 2023 ) . A simple polynomial-time approximation algorithm for the total variation distance between two product distributions . TheoretiCS
Anand K, Jerrum M ( 2022 ) . Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing . SIAM Journal on Computing vol. 51 , ( 4 ) 1280 - 1295 .
Guo H, Jerrum M ( 2022 ) . Counting vertices of integral polytopes defined by facets . Discrete and Computational Geometry
Jerrum M, Dyer M, Müller H, Vušković K ( 2021 ) . Counting weighted independent sets beyond the permanent . SIAM Journal on Discrete Mathematics vol. 35 , ( 2 ) 1503 - 1524 .
Jerrum M, Dyer M, Heinrich M, Müller H ( 2021 ) . Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs . Combinatorics, Probability and Computing
Jerrum M, Makai T ( 2021 ) . The Size of the Giant Joint Component in a Binomial Random Double Graph . The Electronic Journal of Combinatorics vol. 28 , ( 1 ) Article 33 ,
Jerrum MR ( 2021 ) . Sharp thresholds of graph properties, and the <i>k</i>-sat problem . BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY vol. 58 , ( 2 ) 267 - 268 .
Jerrum M, Galanis A, Goldberg LA, Vigoda E, Dyer M ( 2020 ) . Random Walks on Small World Networks . ACM Transactions on Algorithms vol. 16 , ( 3 ) Article 37 ,
Jerrum M, Goldberg LA ( 2019 ) . Approximating Pairwise Correlations in the Ising Model . ACM Transactions on Computation Theory vol. 11 , ( 4 ) Article 23 ,
Guo H, Jerrum M ( 2019 ) . A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability . SIAM Journal on Computing vol. 48 , ( 3 ) 964 - 978 .
Guo H, Jerrum M, Liu J ( 2019 ) . Uniform Sampling Through the Lovász Local Lemma . Journal of the ACM vol. 66 , ( 3 ) 1 - 31 .
Guo H, Jerrum M ( 2018 ) . A polynomial-time approximation algorithm for all-terminal network reliability . Leibniz International Proceedings in Informatics, LIPIcs . vol. 107 ,
Guo H, Jerrum M ( 2018 ) . Perfect simulation of the hard disks model by partial rejection sampling . Leibniz International Proceedings in Informatics, LIPIcs . vol. 107 ,
Guo H, JERRUM MR ( 2018 ) . Random cluster dynamics for the Ising model is rapidly mixing . Annals of Applied Probability
Jerrum M, Meeks K ( 2017 ) . The parameterised complexity of counting even and odd induced subgraphs . COMBINATORICA vol. 37 , ( 5 ) 965 - 990 .
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 . Conference: STOC’17, Montreal, Canada vol. Part F128415 , 342 - 355 .
Dyer M, JERRUM MR, Müller H ( 2017 ) . On the switch Markov chain for perfect matchings . Journal of the Association for Computing Machinery (ACM) vol. 64 , ( 2 ) Article 12 ,
Bulatov A, Goldberg LA, Jerrum M, Richerby D, Živný S ( 2017 ) . Functional clones and expressibility of partition functions . Theoretical Computer Science
JERRUM MR, Galanis A, Goldberg LA ( 2017 ) . A complexity trichotomy for approximately counting list H-colourings . ACM Transactions on Computation Theory vol. 9 , ( 2 ) Article 9 ,
Jerrum M ( 2017 ) . Counting Constraint Satisfaction Problems . The Constraint Satisfaction Problem , Editors: Krokhin, AA, Zivný, S , vol. 7 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Goldberg LA, Jerrum M ( 2016 ) . The complexity of counting locally maximal satisfying assignments of Boolean CSPs . Theoretical Computer Science vol. 634 , 35 - 46 .
Galanis A, Goldberg LA, Jerrum M ( 2016 ) . APPROXIMATELY COUNTING H-COLORINGS IS #BIS-HARD . SIAM JOURNAL ON COMPUTING vol. 45 , ( 3 ) 680 - 711 .
Galanis A, Goldberg LA, Jerrum M ( 2016 ) . A Complexity Trichotomy for Approximately Counting List H-Colourings . ICALP . Editors: Chatzigiannakis, I, Mitzenmacher, M, Rabani, Y, Sangiorgi, D et al. , vol. 55 , 46:1 - 46:1 .
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D, 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 .
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 vol. 112 , ( 43 ) 13161 - 13166 .
Jerrum M, Meeks K ( 2015 ) . Some Hard Families of Parameterized Counting Problems . ACM Transactions on Computation Theory vol. 7 , ( 3 ) 1 - 18 .
Galanis A, Goldberg LA, Jerrum M ( 2015 ) . Approximately Counting H-Colourings is #BIS-Hard . Lecture Notes in Computer Science . vol. 9134 , 529 - 541 .
Chen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D ( 2015 ) . The complexity of approximating conservative counting CSPs . Journal of Computer and System Sciences vol. 81 , ( 1 ) 311 - 329 .
Faben J, Jerrum M ( 2015 ) . . Theory of Computing vol. 11 , ( 1 ) 35 - 57 .
Galanis A, Goldberg LA, Jerrum M ( 2015 ) . Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard . ICALP (1) . Editors: Halldórsson, MM, Iwama, K, Kobayashi, N, Speckmann, B et al. , vol. 9134 , 529 - 541 .
Goldberg LA, Jerrum M, McQuillan C ( 2015 ) . Approximating the partition function of planar two-state spin systems . J. Comput. Syst. Sci. vol. 81 , Article 1 , 330 - 358 .
Goldberg LA, Jerrum M ( 2014 ) . The Complexity of Computing the Sign of the Tutte Polynomial . SIAM Journal on Computing vol. 43 , ( 6 ) 1921 - 1952 .
Jerrum M, Meeks K ( 2014 ) . The parameterised complexity of counting connected subgraphs and graph motifs . JOURNAL OF COMPUTER AND SYSTEM SCIENCES vol. 81 , ( 4 ) 702 - 716 .
Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D, Vigoda E ( 2014 ) . BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region . Leibniz International Proceedings in Informatics, LIPIcs . vol. 28 , 582 - 595 .
Goldberg LA, Jerrum M ( 2014 ) . The Complexity of Approximately Counting Tree Homomorphisms . ACM Transactions on Computation Theory vol. 6 , ( 2 ) 1 - 31 .
Bulatov A, Dyer M, Goldberg LA, Jerrum M, McQuillan C ( 2013 ) . The expressibility of functions on the Boolean domain, with applications to Counting CSPs . J. Assoc. Comput. Mach. vol. 60 , ( 5 ) Article 32 ,
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. vol. 42 , Article 3 , 1132 - 1157 .
Goldberg LA, 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 .
Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D ( 2013 ) . The complexity of approximating conservative counting CSPs . STACS . Editors: Portier, N, Wilke, T , vol. 20 , 148 - 159 .
Goldberg LA, Jerrum M ( 2012 ) . A counterexample to rapid mixing of the Ge-Stefankovic process . ELECTRONIC COMMUNICATIONS IN PROBABILITY vol. 17 , 1 - 6 .
Goldberg LA, Jerrum M ( 2012 ) . Approximating the Partition Function of the Ferromagnetic Potts Model . JOURNAL OF THE ACM vol. 59 , ( 5 ) Article ARTN 25 ,
Goldberg LA, Jerrum M, McQuillan C ( 2012 ) . Approximating the partition function of planar two-state spin systems . CoRR vol. abs/1208.4987 ,
Goldberg LA, Jerrum M ( 2012 ) . Inapproximability of the Tutte polynomial of a planar graph . COMPUTATIONAL COMPLEXITY vol. 21 , ( 4 ) 605 - 642 .
Bulatov AA, Dyer ME, Goldberg LA, Jerrum M ( 2012 ) . Log-supermodular functions, functional clones and counting CSPs . STACS . Editors: Dürr, C, Wilke, T , vol. 14 , 302 - 313 .
Goldberg LA, Jerrum M ( 2012 ) . The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) . ICALP (1) . Editors: Czumaj, A, Mehlhorn, K, Pitts, AM, Wattenhofer, R et al. , vol. 7391 , 399 - 410 .
Chen X, Dyer ME, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D ( 2012 ) . The complexity of approximating conservative counting CSPs . CoRR vol. abs/1208.1783 ,
Bulatov A, Dyer M, Goldberg LA, Jalsenius M, Jerrum M, Richerby D ( 2012 ) . The complexity of weighted and unweighted #CSP . JOURNAL OF COMPUTER AND SYSTEM SCIENCES vol. 78 , ( 2 ) 681 - 688 .
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) . Editors: Aceto, L, Henzinger, M, Sgall, J , vol. 6755 , 521 - 532 .
Dyer M, Goldberg LA, Jerrum M ( 2010 ) . A Complexity Dichotomy For Hypergraph Partition Functions . COMPUT COMPLEX vol. 19 , ( 4 ) 605 - 633 .
Jerrum M ( 2010 ) . Technical Perspective Constraint Satisfaction Problems and Computational Complexity . COMMUN ACM vol. 53 , ( 9 ) 98 - 98 .
Goldberg LA, Jerrum M, Karpinski M ( 2010 ) . The Mixing Time of Glauber Dynamics for Coloring Regular Trees . RANDOM STRUCT ALGOR vol. 36 , ( 4 ) 464 - 476 .
Dyer M, Goldberg LA, Jerrum M ( 2010 ) . An approximation trichotomy for Boolean #CSP . J COMPUT SYST SCI vol. 76 , ( 3-4 ) 267 - 277 .
Goldberg LA, Grohe M, Jerrum M, Thurley M ( 2010 ) . A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH MIXED SIGNS . SIAM J COMPUT vol. 39 , ( 7 ) 3336 - 3402 .
Goldberg LA, Jerrum M ( 2010 ) . Approximating the Partition Function of the Ferromagnetic Potts Model . AUTOMATA, LANGUAGES AND PROGRAMMING, PT I . Editors: Abramsky, S, Gavoille, C, Kirchner, C, MeyerAufDerHeide, F et al. , vol. 6198 , 396 - 407 .
Goldberg LA, Jerrum M ( 2010 ) . Approximating the Partition Function of the Ferromagnetic Potts Model . ICALP (1) . Editors: Abramsky, S, Gavoille, C, Kirchner, C, Heide, FMAD et al. , vol. 6198 , 396 - 407 .
Dyer M, Goldberg LA, Jerrum M ( 2009 ) . MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS . ANN APPL PROBAB vol. 19 , ( 1 ) 71 - 107 .
Goldberg LA, Grohe M, Jerrum M, Thurley M ( 2009 ) . A Complexity Dichotomy for Partition Functions with Mixed Signs . STACS . Editors: Albers, S, Marion, J-Y , vol. 3 , 493 - 504 .
Dyer M, Goldberg LA, Jerrum M ( 2008 ) . Dobrushin Conditions and Systematic Scan . COMB PROBAB COMPUT vol. 17 , ( 6 ) 761 - 779 .
Goldberg LA, Jerrum M ( 2008 ) . Inapproximability of the Tutte polynomial . INFORM COMPUT vol. 206 , ( 7 ) 908 - 929 .
Dyer M, Goldberg LA, Jerrum M ( 2008 ) . THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP . SIAM J COMPUT vol. 38 , ( 5 ) 1970 - 1986 .
Goldberg LA, Jerrum M ( 2007 ) . Inapproximability of the Tutte Polynomial . STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING . 459 - 468 .
Goldberg LA, Jerrum M ( 2007 ) . Inapproximability of the Tutte polynomial . STOC . Editors: Johnson, DS, Feige, U , 459 - 468 .
Goldberg LA, Jerrum M ( 2007 ) . The complexity of ferromagnetic ising with local fields . COMB PROBAB COMPUT vol. 16 , ( 1 ) 43 - 61 .
Jerrum M ( 2006 ) . On the approximation of one Markov chain by another . PROBAB THEORY REL vol. 135 , ( 1 ) 1 - 14 .
Dyer M, Goldberg LA, Jerrum M ( 2006 ) . Systematic scan for sampling colorings . ANN APPL PROBAB vol. 16 , ( 1 ) 185 - 230 .
Dyer ME, Goldberg LA, Jerrum M ( 2006 ) . Dobrushin Conditions and Systematic Scan . APPROX-RANDOM . Editors: Díaz, J, Jansen, K, Rolim, JDP, Zwick, U et al. , vol. 4110 , 327 - 338 .
Dyer M, Goldberg LA, Jerrum M ( 2006 ) . Dobrushin conditions and systematic scan . APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES . Editors: Draz, J, Jansen, K, Rolim, JDP, Zwick, U et al. , vol. 4110 , 327 - 338 .
JERRUM MR, Martin R, Dyer M, Goldberg LA ( 2006 ) . Markov chain comparison . Probability Surveys vol. 3 , 89 - 111 .
Cryan M, Dyer M, Goldberg LA, Jerrum M, 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 .
Jerrum M ( 2006 ) . Two remarks concerning balanced matroids . COMBINATORICA vol. 26 , ( 6 ) 733 - 742 .
Jerrum M, Son JB, Tetali P, Vigoda E ( 2004 ) . Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains . ANN APPL PROBAB vol. 14 , ( 4 ) 1741 - 1765 .
Jerrum M, Sinclair A, Vigoda E ( 2004 ) . A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries . J ACM vol. 51 , ( 4 ) 671 - 697 .
Dyer M, Jerrum M, 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 .
Dyer M, Goldberg LA, Greenhill C, Jerrum M ( 2004 ) . The relative complexity of approximate counting problems . ALGORITHMICA vol. 38 , ( 3 ) 471 - 500 .
Dyer M, Goldberg LA, Jerrum M ( 2004 ) . Counting and sampling H-colourings . INFORM COMPUT vol. 189 , ( 1 ) 1 - 16 .
Goldberg LA, Jerrum M, Kannan S, Paterson M ( 2004 ) . A bound on the capacity of backoff and acknowledgment-based protocols . SIAM J COMPUT vol. 33 , ( 2 ) 313 - 331 .
Goldberg LA, Jerrum M, Paterson M ( 2003 ) . The computational complexity of two-state spin systems . RANDOM STRUCT ALGOR vol. 23 , ( 2 ) 133 - 154 .
Jerrum M ( 2003 ) . Counting, Sampling and Integrating: Algorithm and Complexity . Springer Nature
Dyer M, Frieze A, Jerrum M ( 2002 ) . On counting independent sets in sparse graphs . SIAM JOURNAL ON COMPUTING . vol. 31 , 1527 - 1541 .
Dyer M, Goldberg LA, Greenhill C, Istrate G, Jerrum M ( 2002 ) . Convergence of the iterated prisoner's dilemma game . COMB PROBAB COMPUT vol. 11 , ( 2 ) 135 - 147 .
Dyer ME, Goldberg LA, Jerrum M ( 2002 ) . Counting and Sampling H-Colourings . RANDOM . Editors: Rolim, JDP, Vadhan, SP , vol. 2483 , 51 - 67 .
Dyer ME, Jerrum M, Vigoda E ( 2002 ) . Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs . RANDOM . Editors: Rolim, JDP, Vadhan, SP , vol. 2483 , 68 - 77 .
Cryan M, Dyer M, Goldberg LA, Jerrum M, Martin R ( 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 . 711 - 720 .
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 . 721 - 729 .
Goldberg LA, Jerrum M ( 2002 ) . The 'Burnside process' converges slowly . COMB PROBAB COMPUT vol. 11 , ( 1 ) 21 - 34 .
Jerrum M, Sinclair A, Vigoda E ( 2001 ) . A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries . STOC . Editors: Vitter, JS, Spirakis, PG, Yannakakis, M , 712 - 721 .
Dyer M, Goldberg LA, Greenhill C, Jerrum M, 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 .
Dyer ME, Jerrum M, Vigoda E ( 2001 ) . Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs . Graphs, Morphisms and Statistical Physics . Editors: Nesetril, J, Winkler, P , vol. 63 , 87 - 95 .
Back to Search