×
Compute Distance To:
Author ID: jerrum.mark-r Recent zbMATH articles by "Jerrum, Mark R."
Published as: Jerrum, Mark; Jerrum, Mark R.; Jerrum, M.
External Links: MGP · Wikidata · dblp · GND · IdRef
Documents Indexed: 131 Publications since 1982, including 1 Book
Co-Authors: 59 Co-Authors with 112 Joint Publications
2,048 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

112 Publications have been cited 1,948 times in 1,220 Documents Cited by Year
Random generation of combinatorial structures from a uniform distribution. Zbl 0597.68056
Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V.
189
1986
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
138
2004
Approximate counting, uniform generation and rapidly mixing Markov chains. Zbl 0668.05060
Sinclair, Alistair; Jerrum, Mark
134
1989
Approximating the permanent. Zbl 0723.05107
Jerrum, Mark; Sinclair, Alistair
132
1989
Polynomial-time approximation algorithms for the Ising model. Zbl 0782.05076
Jerrum, Mark; Sinclair, Alistar
99
1993
Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION. Zbl 0873.68078
Frieze, A.; Jerrum, M.
82
1997
A very simple algorithm for estimating the number of \(k\)-colorings of a low-degree graph. Zbl 0833.60070
Jerrum, Mark
70
1995
Counting, sampling and integrating: algorithms and complexity. Zbl 1011.05001
Jerrum, Mark
56
2003
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
50
2004
Large cliques elude the Metropolis process. Zbl 0754.60018
Jerrum, Mark
45
1992
On counting independent sets in sparse graphs. Zbl 1041.68045
Dyer, Martin; Frieze, Alan; Jerrum, Mark
37
2002
The complexity of weighted Boolean #CSP. Zbl 1191.68351
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
37
2009
Some exact complexity results for straight-line computations over semirings. Zbl 0485.68038
Jerrum, Mark; Snir, Marc
37
1982
The complexity of finding minimum-length generator sequences. Zbl 0564.68031
Jerrum, Mark R.
31
1985
A polynomial algorithm for deciding bisimilarity of normed context-free processes. Zbl 0871.68086
Hirshfeld, Yoram; Jerrum, Mark; Moller, Faron
31
1996
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
29
2008
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
28
2010
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Zbl 0831.68087
Goldberg, Paul W.; Jerrum, Mark R.
28
1995
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Zbl 1067.60065
Jerrum, Mark; Son, Jung-Bae; Tetali, Prasad; Vigoda, Eric
28
2004
Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION. Zbl 1135.90420
Frieze, Alan; Jerrum, Mark
26
1995
Three-dimensional statistical data security problems. Zbl 0802.68046
Irving, Robert W.; Jerrum, Mark R.
25
1994
Markov chain comparison. Zbl 1189.60135
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
24
2006
Fast uniform generation of regular graphs. Zbl 0694.68044
Jerrum, Mark; Sinclair, Alistair
24
1990
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
23
2010
The computational complexity of two-state spin systems. Zbl 1030.82001
Goldberg, Leslie Ann; Jerrum, Mark; Paterson, Mike
23
2003
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
22
2012
A polynomial-time algorithm for deciding bisimulation equivalence of normed basic parallel processes. Zbl 0857.68042
Hirshfeld, Yoram; Jerrum, Mark; Moller, Faron
20
1996
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. Zbl 1117.62062
Cryan, Mary; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
18
2006
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
17
2007
The Metropolis algorithm for graph bisection. Zbl 0932.60079
Jerrum, Mark; Sorkin, Gregory B.
17
1998
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Zbl 1323.68571
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric
17
2001
The Swendsen-Wang process does not always mix rapidly. Zbl 1006.82015
Gore, Vivek K.; Jerrum, Mark R.
15
1999
A compact representation for permutation groups. Zbl 0597.68036
Jerrum, Mark
13
1986
Bisimulation equivalence is decidable for normed process algebra. (Extended abstract). Zbl 0941.68574
Hirshfeld, Yoram; Jerrum, Mark
13
1999
The expressibility of functions on the Boolean domain, with applications to counting CSPs. Zbl 1281.68131
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Mcquillan, Colin
13
2013
Generating and counting Hamilton cycles in random regular graphs. Zbl 0857.68084
Frieze, Alan; Jerrum, Mark; Molloy, Michael; Robinson, Robert; Wormald, Nicholas
13
1996
Systematic scan for sampling colorings. Zbl 1095.60024
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
12
2006
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric
12
2016
The parameterised complexity of counting connected subgraphs and graph motifs. Zbl 1320.68101
Jerrum, Mark; Meeks, Kitty
11
2015
The complexity of weighted and unweighted \(\#\)CSP. Zbl 1282.68110
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David
11
2012
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
11
2004
Random cluster dynamics for the Ising model is rapidly mixing. Zbl 1419.82013
Guo, Heng; Jerrum, Mark
11
2017
When is a graphical sequence stable? Zbl 0819.05052
Jerrum, Mark; Sinclair, Alistair; McKay, Brendan
10
1992
An analysis of Monte Carlo algorithm for estimating the permanent. Zbl 0817.68087
Frieze, Alan; Jerrum, Mark
10
1995
On approximately counting colorings of small degree graphs. Zbl 0937.05041
Bubley, Russ; Dyer, Martin; Greenhill, Catherine; Jerrum, Mark
9
1998
Approximately counting Hamilton paths and cycles in dense graphs. Zbl 0907.68111
Dyer, Martin; Frieze, Alan; Jerrum, Mark
8
1998
On the switch Markov chain for perfect matchings. Zbl 1426.60097
Dyer, Martin; Jerrum, Mark; Müller, Haiko
8
2017
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
7
2008
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
7
2015
Two remarks concerning balanced matroids. Zbl 1121.05027
Jerrum, Mark
7
2006
The parameterised complexity of counting even and odd induced subgraphs. Zbl 1413.68063
Jerrum, Mark; Meeks, Kitty
6
2017
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
2010
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2009
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
Mathematical foundations of the Markov chain Monte Carlo method. Zbl 0920.65001
Jerrum, Mark
6
1998
Counting and sampling \(H\)-colourings. Zbl 1082.68079
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2004
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
6
2016
Random cluster dynamics for the Ising model is rapidly mixing. Zbl 1395.82133
Guo, Heng; Jerrum, Mark
6
2018
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
6
2015
Approximately counting Hamilton cycles in dense graphs. Zbl 0867.05030
Dyer, Martin; Frieze, Alan; Jerrum, Mark
5
1994
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
5
2015
Polynomial-time approximation algorithms for the Ising model (extended abstract). Zbl 0764.65091
Jerrum, Mark; Sinclair, Alistair
5
1990
Inapproximability of the Tutte polynomial. Zbl 1232.68073
Goldberg, Leslie Ann; Jerrum, Mark
5
2007
The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122
Faben, John; Jerrum, Mark
5
2015
The Swendsen-Wang process does not always mix rapidly. Zbl 0963.68216
Gore, Vivek K.; Jerrum, Mark R.
5
1999
Convergence of the iterated prisoner’s dilemma game. Zbl 1006.60009
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark
5
2002
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
A mildly exponential approximation algorithm for the permanent. Zbl 0857.68053
Jerrum, M.; Vazirani, U.
5
1996
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
4
2013
The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation). Zbl 1272.68155
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
Counting trees in a graph is \(\# \text{P}\)-complete. Zbl 0809.68076
Jerrum, Mark
4
1994
On continuous homotopic one layer routing. Zbl 0662.68120
Gao, Shaodi; Jerrum, Mark; Kaufmann, Michael; Mehlhorn, Kurt; Rülling, Wolfgang; Storb, Christoph
4
1988
Doubly logarithmic communication algorithms for optical-communication parallel computers. Zbl 0885.68079
Goldberg, Leslie Ann; Jerrum, Mark; Leighton, Tom; Rao, Satish
4
1997
The “Markov chain Monte Carlo” method: Analytical techniques and applications. Zbl 0832.60076
Jerrum, Mark
4
1995
Dobrushin conditions and systematic scan. Zbl 1155.60331
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2006
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
4
2019
An extension of path coupling and its application to the Glauber dynamics for graph colorings. Zbl 0999.05035
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
3
2001
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1333.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2011
A mildly exponential approximation algorithm for the permanent. Zbl 0919.68057
Jerrum, Mark; Vazirani, Umesh
3
1992
An analysis of a Monte Carlo algorithm for estimating the permanent. Zbl 0925.68209
Jerrum, Mark
3
1993
An elementary analysis of a procedure for sampling points in a convex body. Zbl 0972.60037
Bubley, Russ; Dyer, Martin; Jerrum, Mark
3
1998
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David
3
2013
Uniform sampling through the Lovász local lemma. Zbl 1370.68324
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
3
2017
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
Counting unlabelled subtrees of a tree is \(\# P\)-complete. Zbl 0951.68047
Goldberg, Leslie Ann; Jerrum, Mark
3
2000
A quasi-polynomial-time algorithm for sampling words from a context-free language. Zbl 0879.68065
Gore, Vivek; Jerrum, Mark; Kannan, Sampath; Sweedyk, Z.; Mahaney, Steve
3
1997
Approximating the Tutte polynomial. Zbl 1130.05016
Jerrum, Mark
3
2007
Log-supermodular functions, functional clones and counting CSPs. Zbl 1245.68100
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
2
2012
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
Rapidly mixing Markov chains for dismantleable constraint graphs. Zbl 1028.68099
Dyer, Martin; Jerrum, Mark; Vigoda, Eric
2
2002
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1272.05019
Goldberg, Leslie Ann; Jerrum, Mark
2
2013
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
2
2002
Families of fixed degree graphs for processor interconnection. Zbl 0529.68037
Jerrum, Mark R.; Skyum, Sven
2
1984
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). Zbl 0981.05046
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
2
2000
Computational Pólya theory. Zbl 0833.20005
Jerrum, Mark
2
1995
Rapidly mixing Markov chains for dismantleable constraint graphs. Zbl 1061.05031
Dyer, Martin; Jerrum, Mark; Vigoda, Eric
2
2004
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
The complexity of computing the sign of the Tutte polynomial. Zbl 1437.68068
Goldberg, Leslie Ann; Jerrum, Mark
2
2014
Random walks on small world networks. Zbl 07342480
Dyer, Martin E.; Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark; Vigoda, Eric
1
2020
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
4
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
A polynomial-time approximation algorithm for all-terminal network reliability. Zbl 1430.68441
Guo, Heng; Jerrum, Mark
2
2019
Random cluster dynamics for the Ising model is rapidly mixing. Zbl 1395.82133
Guo, Heng; Jerrum, Mark
6
2018
Random cluster dynamics for the Ising model is rapidly mixing. Zbl 1419.82013
Guo, Heng; Jerrum, Mark
11
2017
On the switch Markov chain for perfect matchings. Zbl 1426.60097
Dyer, Martin; Jerrum, Mark; Müller, Haiko
8
2017
The parameterised complexity of counting even and odd induced subgraphs. Zbl 1413.68063
Jerrum, Mark; Meeks, Kitty
6
2017
Uniform sampling through the Lovász local lemma. Zbl 1370.68324
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
3
2017
Functional clones and expressibility of partition functions. Zbl 1418.08001
Bulatov, Andrei; Goldberg, Leslie Ann; Jerrum, Mark; Richerby, David; Živný, Stanislav
1
2017
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
1
2017
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric
12
2016
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
6
2016
The complexity of counting locally maximal satisfying assignments of Boolean CSPs. Zbl 1339.68117
Goldberg, Leslie Ann; Jerrum, Mark
1
2016
On the switch Markov chain for perfect matchings. Zbl 1412.60105
Dyer, Martin; Jerrum, Mark; Müller, Haiko
1
2016
The parameterised complexity of counting connected subgraphs and graph motifs. Zbl 1320.68101
Jerrum, Mark; Meeks, Kitty
11
2015
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
7
2015
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
6
2015
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
5
2015
The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122
Faben, John; Jerrum, Mark
5
2015
Approximating the partition function of planar two-state spin systems. Zbl 1401.05279
Goldberg, Leslie Ann; Jerrum, Mark; McQuillan, Colin
2
2015
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
The complexity of computing the sign of the Tutte polynomial. Zbl 1437.68068
Goldberg, Leslie Ann; Jerrum, Mark
2
2014
The expressibility of functions on the Boolean domain, with applications to counting CSPs. Zbl 1281.68131
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Mcquillan, Colin
13
2013
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
4
2013
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David
3
2013
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1272.05019
Goldberg, Leslie Ann; Jerrum, Mark
2
2013
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
22
2012
The complexity of weighted and unweighted \(\#\)CSP. Zbl 1282.68110
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David
11
2012
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation). Zbl 1272.68155
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
Log-supermodular functions, functional clones and counting CSPs. Zbl 1245.68100
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
2
2012
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1333.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2011
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
28
2010
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
23
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
2010
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
A complexity dichotomy for hypergraph partition functions. Zbl 1217.68105
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
1
2010
The complexity of weighted Boolean #CSP. Zbl 1191.68351
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
37
2009
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2009
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
29
2008
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
7
2008
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
17
2007
Inapproximability of the Tutte polynomial. Zbl 1232.68073
Goldberg, Leslie Ann; Jerrum, Mark
5
2007
Approximating the Tutte polynomial. Zbl 1130.05016
Jerrum, Mark
3
2007
Markov chain comparison. Zbl 1189.60135
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
24
2006
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. Zbl 1117.62062
Cryan, Mary; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
18
2006
Systematic scan for sampling colorings. Zbl 1095.60024
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
12
2006
Two remarks concerning balanced matroids. Zbl 1121.05027
Jerrum, Mark
7
2006
Dobrushin conditions and systematic scan. Zbl 1155.60331
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2006
On the approximation of one Markov chain by another. Zbl 1114.60058
Jerrum, Mark
1
2006
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
138
2004
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
50
2004
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Zbl 1067.60065
Jerrum, Mark; Son, Jung-Bae; Tetali, Prasad; Vigoda, Eric
28
2004
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
11
2004
Counting and sampling \(H\)-colourings. Zbl 1082.68079
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2004
Rapidly mixing Markov chains for dismantleable constraint graphs. Zbl 1061.05031
Dyer, Martin; Jerrum, Mark; Vigoda, Eric
2
2004
Counting, sampling and integrating: algorithms and complexity. Zbl 1011.05001
Jerrum, Mark
56
2003
The computational complexity of two-state spin systems. Zbl 1030.82001
Goldberg, Leslie Ann; Jerrum, Mark; Paterson, Mike
23
2003
On counting independent sets in sparse graphs. Zbl 1041.68045
Dyer, Martin; Frieze, Alan; Jerrum, Mark
37
2002
Convergence of the iterated prisoner’s dilemma game. Zbl 1006.60009
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark
5
2002
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
Rapidly mixing Markov chains for dismantleable constraint graphs. Zbl 1028.68099
Dyer, Martin; Jerrum, Mark; Vigoda, Eric
2
2002
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
2
2002
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Zbl 1323.68571
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric
17
2001
An extension of path coupling and its application to the Glauber dynamics for graph colorings. Zbl 0999.05035
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
3
2001
Counting unlabelled subtrees of a tree is \(\# P\)-complete. Zbl 0951.68047
Goldberg, Leslie Ann; Jerrum, Mark
3
2000
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). Zbl 0981.05046
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
2
2000
Randomly sampling molecules. Zbl 0958.68138
Goldberg, Leslie Ann; Jerrum, Mark
1
2000
The Swendsen-Wang process does not always mix rapidly. Zbl 1006.82015
Gore, Vivek K.; Jerrum, Mark R.
15
1999
Bisimulation equivalence is decidable for normed process algebra. (Extended abstract). Zbl 0941.68574
Hirshfeld, Yoram; Jerrum, Mark
13
1999
The Swendsen-Wang process does not always mix rapidly. Zbl 0963.68216
Gore, Vivek K.; Jerrum, Mark R.
5
1999
The Metropolis algorithm for graph bisection. Zbl 0932.60079
Jerrum, Mark; Sorkin, Gregory B.
17
1998
On approximately counting colorings of small degree graphs. Zbl 0937.05041
Bubley, Russ; Dyer, Martin; Greenhill, Catherine; Jerrum, Mark
9
1998
Approximately counting Hamilton paths and cycles in dense graphs. Zbl 0907.68111
Dyer, Martin; Frieze, Alan; Jerrum, Mark
8
1998
Mathematical foundations of the Markov chain Monte Carlo method. Zbl 0920.65001
Jerrum, Mark
6
1998
An elementary analysis of a procedure for sampling points in a convex body. Zbl 0972.60037
Bubley, Russ; Dyer, Martin; Jerrum, Mark
3
1998
An \(\omega(\sqrt{\log\log n})\) lower bound for routing in optical networks. Zbl 0907.68098
Goldberg, Leslie Ann; Jerrum, Mark; MacKenzie, Philip D.
1
1998
Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION. Zbl 0873.68078
Frieze, A.; Jerrum, M.
82
1997
Doubly logarithmic communication algorithms for optical-communication parallel computers. Zbl 0885.68079
Goldberg, Leslie Ann; Jerrum, Mark; Leighton, Tom; Rao, Satish
4
1997
A quasi-polynomial-time algorithm for sampling words from a context-free language. Zbl 0879.68065
Gore, Vivek; Jerrum, Mark; Kannan, Sampath; Sweedyk, Z.; Mahaney, Steve
3
1997
A polynomial algorithm for deciding bisimilarity of normed context-free processes. Zbl 0871.68086
Hirshfeld, Yoram; Jerrum, Mark; Moller, Faron
31
1996
A polynomial-time algorithm for deciding bisimulation equivalence of normed basic parallel processes. Zbl 0857.68042
Hirshfeld, Yoram; Jerrum, Mark; Moller, Faron
20
1996
Generating and counting Hamilton cycles in random regular graphs. Zbl 0857.68084
Frieze, Alan; Jerrum, Mark; Molloy, Michael; Robinson, Robert; Wormald, Nicholas
13
1996
A mildly exponential approximation algorithm for the permanent. Zbl 0857.68053
Jerrum, M.; Vazirani, U.
5
1996
A very simple algorithm for estimating the number of \(k\)-colorings of a low-degree graph. Zbl 0833.60070
Jerrum, Mark
70
1995
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Zbl 0831.68087
Goldberg, Paul W.; Jerrum, Mark R.
28
1995
Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION. Zbl 1135.90420
Frieze, Alan; Jerrum, Mark
26
1995
An analysis of Monte Carlo algorithm for estimating the permanent. Zbl 0817.68087
Frieze, Alan; Jerrum, Mark
10
1995
The “Markov chain Monte Carlo” method: Analytical techniques and applications. Zbl 0832.60076
Jerrum, Mark
4
1995
Computational Pólya theory. Zbl 0833.20005
Jerrum, Mark
2
1995
Three-dimensional statistical data security problems. Zbl 0802.68046
Irving, Robert W.; Jerrum, Mark R.
25
1994
Approximately counting Hamilton cycles in dense graphs. Zbl 0867.05030
Dyer, Martin; Frieze, Alan; Jerrum, Mark
5
1994
Counting trees in a graph is \(\# \text{P}\)-complete. Zbl 0809.68076
Jerrum, Mark
4
1994
Polynomial-time approximation algorithms for the Ising model. Zbl 0782.05076
Jerrum, Mark; Sinclair, Alistar
99
1993
An analysis of a Monte Carlo algorithm for estimating the permanent. Zbl 0925.68209
Jerrum, Mark
3
1993
Uniform sampling modulo a group of symmetries using Markov chain simulation. Zbl 0814.68077
Jerrum, Mark
2
1993
Large cliques elude the Metropolis process. Zbl 0754.60018
Jerrum, Mark
45
1992
...and 12 more Documents
all top 5

Cited by 1,670 Authors

40 Goldberg, Leslie Ann
36 Jerrum, Mark R.
29 Dyer, Martin E.
23 Vigoda, Eric
20 Cai, Jin-Yi
17 Barvinok, Alexander I.
16 Frieze, Alan Michael
16 Randall, Dana J.
15 Guo, Heng
14 Sinclair, Alistair
14 Štefankovič, Daniel
13 Galanis, Andreas
11 Bezáková, Ivona
11 Diaconis, Persi Warren
11 Lu, Pinyan
11 Mossel, Elchanan
11 Peres, Yuval
10 Greenhill, Catherine S.
10 Lubetzky, Eyal
10 Sly, Allan
10 Wormald, Nicholas Charles
9 Miklós, István
9 Richerby, David M.
9 Roth, Marc
8 Huber, Mark L.
8 Xu, Dachuan
8 Yukna, Stasys P.
7 Bai, Fengshan
7 Bulatov, Andrei A.
7 Jalsenius, Markus
7 Samorodnitsky, Alex
6 Blanca, Antonio
6 Bordewich, Magnus
6 Chlebus, Bogdan Stanislaw
6 Curticapean, Radu
6 Gritzmann, Peter
6 Jančar, Petr
6 Kayibi, Koko Kalambay
6 Kucera, Antonin
6 Lasota, Sławomir
6 Lecué, Guillaume
6 Liang, Heng
6 Lugosi, Gábor
6 Montanari, Andrea
6 Müller, Haiko
6 Pirzada, Shariefuddin
6 Regts, Guus
6 Spirakis, Paul G.
6 Tetali, Prasad
5 Bhatnagar, Nayantara
5 Cereceda, Luis
5 Dell, Holger
5 Ding, Jian
5 Erdős, Péter L.
5 Fröschle, Sibylle B.
5 Fu, Zhiguo
5 Hayes, Thomas P.
5 Hermon, Jonathan
5 Karpinski, Marek
5 Khare, Kshitij
5 Kijima, Shuji
5 Kowalczyk, Michael
5 Lapinskas, John
5 Lerasle, Matthieu
5 Maffioli, Francesco
5 Mayr, Richard M.
5 Pak, Igor
5 Pascoe Streib, Amanda
5 Patel, Viresh
5 Saloff-Coste, Laurent
5 Srivastava, Piyush
5 Vempala, Santosh S.
5 Welsh, Dominic J. A.
5 Winkler, Peter M.
5 Wu, Chenchen
5 Yamakami, Tomoyuki
5 Yang, Linji
5 Ye, Yinyu
5 Yin, Yitong
4 Anantharamu, Lakshmi
4 Anari, Nima
4 Anjos, Miguel F.
4 Cameron, Peter Jephson
4 Chitturi, Bhadrachalam
4 Cryan, Mary
4 Czerwiński, Wojciech
4 Del Lungo, Alberto
4 Díaz, Josep
4 Efthymiou, Charilaos
4 Elbassioni, Khaled M.
4 Gamarnik, David
4 Gao, Pu
4 Ge, Qi
4 Gheissari, Reza
4 Göbel, Andreas-Nikolas
4 Goldreich, Oded
4 Gurvich, Vladimir A.
4 Johnson, Matthew
4 Khachiyan, Leonid Genrikhovich
4 Kleer, Pieter
...and 1,570 more Authors
all top 5

Cited in 238 Serials

103 Theoretical Computer Science
51 Random Structures & Algorithms
46 Discrete Applied Mathematics
42 Journal of Computer and System Sciences
40 Algorithmica
35 Information and Computation
31 The Annals of Applied Probability
29 Information Processing Letters
27 Combinatorics, Probability and Computing
26 SIAM Journal on Computing
23 Journal of Statistical Physics
20 Probability Theory and Related Fields
18 SIAM Journal on Discrete Mathematics
18 Computational Complexity
17 The Annals of Statistics
17 Theory of Computing Systems
16 Discrete Mathematics
15 Linear Algebra and its Applications
15 Stochastic Processes and their Applications
14 Journal of Combinatorial Optimization
12 Mathematical Programming. Series A. Series B
12 The Electronic Journal of Combinatorics
11 Communications in Mathematical Physics
11 Bernoulli
10 The Annals of Probability
10 Advances in Applied Mathematics
8 Journal of Mathematical Physics
8 Distributed Computing
8 Journal of Statistical Mechanics: Theory and Experiment
7 Israel Journal of Mathematics
7 Journal of Combinatorial Theory. Series B
7 European Journal of Combinatorics
7 Combinatorica
7 International Journal of Foundations of Computer Science
7 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques
7 Electronic Journal of Statistics
6 Journal of Applied Probability
6 Journal of Symbolic Computation
6 Journal of Complexity
6 European Journal of Operational Research
5 Advances in Mathematics
5 Applied Mathematics and Computation
5 Statistics & Probability Letters
5 Graphs and Combinatorics
5 Journal of Theoretical Probability
5 Annals of Operations Research
5 Journal of Machine Learning Research (JMLR)
5 Journal of Discrete Algorithms
5 Algorithms
4 Journal of Combinatorial Theory. Series A
4 Discrete & Computational Geometry
4 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI
4 Electronic Journal of Probability
4 Constraints
4 Foundations of Computational Mathematics
4 Discrete Mathematics, Algorithms and Applications
4 Statistics and Computing
4 ACM Transactions on Computation Theory
3 Artificial Intelligence
3 Journal of Computational and Applied Mathematics
3 Mathematics of Operations Research
3 Operations Research
3 Operations Research Letters
3 Order
3 Statistical Science
3 Computers & Operations Research
3 Journal of Cryptology
3 Neural Networks
3 Journal of Global Optimization
3 Journal of Statistical Computation and Simulation
3 Bulletin of the American Mathematical Society. New Series
3 Cybernetics and Systems Analysis
3 Applied and Computational Harmonic Analysis
3 Optimization Methods & Software
3 Acta Mathematica Sinica. English Series
3 Methodology and Computing in Applied Probability
3 Stochastic Models
3 Discrete Optimization
3 Frontiers of Mathematics in China
3 Forum of Mathematics, Sigma
3 Computer Science Review
2 Advances in Applied Probability
2 Communications in Algebra
2 Computers & Mathematics with Applications
2 Communications on Pure and Applied Mathematics
2 Journal of Computational Physics
2 Journal of the Franklin Institute
2 Journal of Mathematical Analysis and Applications
2 Linear and Multilinear Algebra
2 Mathematics of Computation
2 Journal of Mathematical Economics
2 Mathematika
2 Systems & Control Letters
2 Optimization
2 Sequential Analysis
2 Machine Learning
2 Computational Geometry
2 Computational Statistics
2 International Journal of Computer Mathematics
2 Proceedings of the National Academy of Sciences of the United States of America
...and 138 more Serials
all top 5

Cited in 47 Fields

608 Computer science (68-XX)
435 Combinatorics (05-XX)
308 Probability theory and stochastic processes (60-XX)
178 Operations research, mathematical programming (90-XX)
120 Statistical mechanics, structure of matter (82-XX)
112 Numerical analysis (65-XX)
103 Statistics (62-XX)
54 Linear and multilinear algebra; matrix theory (15-XX)
36 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
34 Information and communication theory, circuits (94-XX)
31 Biology and other natural sciences (92-XX)
25 Quantum theory (81-XX)
24 Group theory and generalizations (20-XX)
18 Mathematical logic and foundations (03-XX)
17 Convex and discrete geometry (52-XX)
14 Number theory (11-XX)
12 Order, lattices, ordered algebraic structures (06-XX)
7 Dynamical systems and ergodic theory (37-XX)
7 Manifolds and cell complexes (57-XX)
6 Partial differential equations (35-XX)
5 Commutative algebra (13-XX)
5 Calculus of variations and optimal control; optimization (49-XX)
5 Global analysis, analysis on manifolds (58-XX)
4 Measure and integration (28-XX)
4 Operator theory (47-XX)
4 Systems theory; control (93-XX)
3 General algebraic systems (08-XX)
3 Field theory and polynomials (12-XX)
3 Functions of a complex variable (30-XX)
3 Approximations and expansions (41-XX)
3 Integral transforms, operational calculus (44-XX)
3 Functional analysis (46-XX)
3 Differential geometry (53-XX)
2 Real functions (26-XX)
2 Special functions (33-XX)
2 Harmonic analysis on Euclidean spaces (42-XX)
2 Geometry (51-XX)
2 Algebraic topology (55-XX)
2 Mechanics of deformable solids (74-XX)
2 Fluid mechanics (76-XX)
2 Optics, electromagnetic theory (78-XX)
1 General and overarching topics; collections (00-XX)
1 Associative rings and algebras (16-XX)
1 Category theory; homological algebra (18-XX)
1 Difference and functional equations (39-XX)
1 Abstract harmonic analysis (43-XX)
1 Integral equations (45-XX)

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.