Menu
 
Research menu
Jump to menu

Publications:  Prof Mark Jerrum

Guo H, Jerrum M(2019). A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. SIAM Journal on Computing vol. 48, (3) 964-978.
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 vol. 66, (3)
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
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. Editors: Chatzigiannakis, I, Kaklamanis, C, Marx, D, Sannella, D et al., vol. 107, 68:1-68:1.
Guo H, Jerrum M (2018). Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. ICALP. Editors: Chatzigiannakis, I, Kaklamanis, C, Marx, D, Sannella, D et al., vol. 107, 69:1-69:1.
Jerrum M, Meeks K(2017). The parameterised complexity of counting even and odd induced subgraphs. COMBINATORICA vol. 37, (5) 965-990.
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. Conference: STOC’17, Montreal, Canada vol. Part F128415, 342-355.
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) vol. 64, (2) Article 12,
10.1145/2822322
https://qmro.qmul.ac.uk/xmlui/handle/123456789/22454
Bulatov A, Goldberg LA, Jerrum M, Richerby D, Živný S(2017). Functional clones and expressibility of partition functions. Theoretical Computer Science
10.1016/j.tcs.2017.05.001
https://qmro.qmul.ac.uk/xmlui/handle/123456789/23690
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,
10.1145/3037381
https://qmro.qmul.ac.uk/xmlui/handle/123456789/22421
Jerrum M(2017). Counting Constraint Satisfaction Problems. The Constraint Satisfaction Problem, Editors: Krokhin, AA, Zivny, S, vol. 7, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Goldberg LA, Jerrum M(2016). The complexity of counting locally maximal satisfying assignments of Boolean CSPs. THEORETICAL COMPUTER SCIENCE vol. 634, 35-46.
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 vol. 45, (3) 680-711.
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. 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(2016). #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.
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 vol. 112, (43) 13161-13166.
10.1073/pnas.1505664112
Jerrum M, Meeks K(2015). Some Hard Families of Parameterized Counting Problems. ACM Transactions on Computation Theory vol. 7, (3) 1-18.
10.1145/2786017
Galanis A, Goldberg LA, Jerrum M (2015). Approximately Counting H-Colourings is #BIS-Hard. Automata, Languages, and Programming, Pt I. vol. 9134, 529-541.
10.1007/978-3-662-47672-7_43
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.
Faben J, Jerrum M(2015). The Complexity of Parity Graph Homomorphism: An Initial Investigation. Theory of Computing vol. 11, 35-57.
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.
10.1016/j.jcss.2014.06.006
https://qmro.qmul.ac.uk/xmlui/handle/123456789/30088
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.
10.1016/j.jcss.2014.11.015
https://qmro.qmul.ac.uk/xmlui/handle/123456789/18887
Goldberg LA, Jerrum M(2014). The Complexity of Approximately Counting Tree Homomorphisms. ACM Transactions on Computation Theory vol. 6, (2) 1-31.
10.1145/2600917
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.
10.4230/LIPIcs.APPROX-RANDOM.2014.582
Goldberg LA, Jerrum M(2014). THE COMPLEXITY OF COMPUTING THE SIGN OF THE TUTTE POLYNOMIAL. SIAM JOURNAL ON COMPUTING vol. 43, (6) 1921-1952.
10.1137/12088330X
https://qmro.qmul.ac.uk/xmlui/handle/123456789/7564
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,
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 vol. 79, (1) 68-78.
10.1016/j.jcss.2012.04.005
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.
10.1137/110851213
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). Inapproximability of the Tutte polynomial of a planar graph. COMPUTATIONAL COMPLEXITY vol. 21, (4) 605-642.
10.1007/s00037-012-0046-4
Goldberg LA, Jerrum M(2012). Approximating the Partition Function of the Ferromagnetic Potts Model. JOURNAL OF THE ACM vol. 59, (5) Article ARTN 25,
10.1145/2371656.2371660
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.
10.1016/j.jcss.2011.12.002
Goldberg LA, Jerrum M(2012). A counterexample to rapid mixing of the Ge-Stefankovic process. ELECTRONIC COMMUNICATIONS IN PROBABILITY vol. 17, 1-6.
10.1214/ECP.v17-1712
Goldberg LA, Jerrum M, McQuillan C(2012). Approximating the partition function of planar two-state spin systems. CoRR vol. abs/1208.4987,
10.1016/j.jcss.2014.06.007
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,
10.4230/LIPIcs.STACS.2013.148
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.
10.1007/s00037-010-0300-6
Jerrum M(2010). Technical Perspective Constraint Satisfaction Problems and Computational Complexity. COMMUN ACM vol. 53, (9) 98-98.
10.1145/1810891.1810913
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.
10.1002/rsa.20303
Dyer M, Goldberg LA, Jerrum M(2010). An approximation trichotomy for Boolean #CSP. J COMPUT SYST SCI vol. 76, (3-4) 267-277.
10.1016/j.jcss.2009.08.003
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.
10.1137/090757496
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.
Dyer M, Goldberg LA, Jerrum M(2009). MATRIX NORMS AND RAPID MIXING FOR SPIN SYSTEMS. ANN APPL PROBAB vol. 19, (1) 71-107.
10.1214/08-AAP532
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.
10.1017/S0963548308009437
Goldberg LA, Jerrum M(2008). Inapproximability of the Tutte polynomial. INFORM COMPUT vol. 206, (7) 908-929.
10.1016/j.ic.2008.04.003
Dyer M, Goldberg LA, Jerrum M(2008). THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP. SIAM J COMPUT vol. 38, (5) 1970-1986.
10.1137/070690201
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.
10.1145/1250790.1250858
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.
10.1017/S096354830600767X
Jerrum M(2006). On the approximation of one Markov chain by another. PROBAB THEORY REL vol. 135, (1) 1-14.
10.1007/s00440-005-0453-4
Dyer M, Goldberg LA, Jerrum M(2006). Systematic scan for sampling colorings. ANN APPL PROBAB vol. 16, (1) 185-230.
10.1214/105051605000000683
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.
10.1214/154957806000000041
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.
10.1137/S0097539703434243
Jerrum M(2006). Two remarks concerning balanced matroids. COMBINATORICA vol. 26, (6) 733-742.
10.1007/s00493-006-0039-5
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.
10.1214/105051604000000639
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.
10.1145/1008731.1008738
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.
10.1002/rsa.20010
Dyer M, Goldberg LA, Greenhill C, Jerrum M(2004). The relative complexity of approximate counting problems. ALGORITHMICA vol. 38, (3) 471-500.
10.1007/s00453-003-1073-y
Dyer M, Goldberg LA, Jerrum M(2004). Counting and sampling H-colourings. INFORM COMPUT vol. 189, (1) 1-16.
10.1016/j.ic.2003.09.001
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.
10.1137/S0097539700381851
Goldberg LA, Jerrum M, Paterson M(2003). The computational complexity of two-state spin systems. RANDOM STRUCT ALGOR vol. 23, (2) 133-154.
10.1002/rsa.10090
Dyer M, Frieze A, Jerrum M (2002). On counting independent sets in sparse graphs. SIAM JOURNAL ON COMPUTING. vol. 31, 1527-1541.
10.1137/S0097539701383844
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.
10.1017/S096354830100503X
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.
10.1109/SFCS.2002.1181996
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.
10.1109/SFCS.2002.1181997
Goldberg LA, Jerrum M(2002). The 'Burnside process' converges slowly. COMB PROBAB COMPUT vol. 11, (1) 21-34.
10.1017/S096354830100493X
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.
10.1137/S0097539700372708
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-96.
Return to top