Publications: Prof Mark Jerrum
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
.