☰

Mark Richard Jerrum - Publications

Affiliations: 
1988 University of Edinburgh, Edinburgh, Scotland, United Kingdom 
Tree Info Similar researchers PubMed Report error

87 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Goldberg LA, Jerrum M. Approximating Pairwise Correlations in the Ising Model Acm Transactions On Computation Theory. 11: 23. DOI: 10.1145/3337785  0.37
2019 Guo H, Jerrum M, Liu J. Uniform Sampling Through the Lovász Local Lemma Journal of the Acm. 66: 18. DOI: 10.1145/3310131  0.352
2019 Guo H, Jerrum M. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability Siam Journal On Computing. 48: 964-978. DOI: 10.1137/18M1201846  0.446
2017 Galanis A, Goldberg LA, Jerrum M. A Complexity Trichotomy for Approximately Counting List H -Colorings Acm Transactions On Computation Theory. 9: 9. DOI: 10.1145/3037381  0.46
2017 Bulatov A, Goldberg LA, Jerrum M, Richerby D, Živný S. Functional clones and expressibility of partition functions Theoretical Computer Science. 687: 11-39. DOI: 10.1016/J.Tcs.2017.05.001  0.311
2017 Jerrum M, Meeks K. The parameterised complexity of counting even and odd induced subgraphs Combinatorica. 37: 965-990. DOI: 10.1007/S00493-016-3338-5  0.432
2016 Dyer M, Jerrum M, Miiller H. On the switch Markov chain for perfect matchings Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 3: 1972-1983. DOI: 10.1145/2822322  0.428
2016 Galanis A, Goldberg LA, Jerrum M. Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard Siam Journal On Computing. 45: 680-711. DOI: 10.1137/15M1020551  0.45
2015 Faben JD, Jerrum M. The Complexity of Parity Graph Homomorphism: An Initial Investigation Theory of Computing. 11: 35-57. DOI: 10.4086/Toc.2015.V011A002  0.472
2015 Jerrum M, Meeks K. Some hard families of parameterized counting problems Acm Transactions On Computation Theory. 7. DOI: 10.1145/2786017  0.439
2015 Galanis A, Goldberg LA, Jerrum M. Approximately counting h-colourings is #bis-hard Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9134: 529-541. DOI: 10.1137/15M1020551  0.444
2015 Goldberg LA, Jerrum M. The complexity of counting locally maximal satisfying assignments of Boolean CSPs Theoretical Computer Science. DOI: 10.1016/J.Tcs.2016.04.008  0.397
2015 Jerrum M, Meeks K. The parameterised complexity of counting connected subgraphs and graph motifs Journal of Computer and System Sciences. 81: 702-716. DOI: 10.1016/J.Jcss.2014.11.015  0.481
2015 Goldberg LA, Jerrum M, McQuillan C. Approximating the partition function of planar two-state spin systems Journal of Computer and System Sciences. 81: 330-358. DOI: 10.1016/J.Jcss.2014.06.007  0.446
2015 Chen X, Dyer M, Goldberg LA, Jerrum M, Lu P, McQuillan C, Richerby D. The complexity of approximating conservative counting CSPs Journal of Computer and System Sciences. 81: 311-329. DOI: 10.1016/J.Jcss.2014.06.006  0.36
2014 Goldberg LA, Jerrum M. The complexity of approximately counting tree homomorphisms Acm Transactions On Computation Theory. 6. DOI: 10.1145/2600917  0.389
2014 Goldberg LA, Jerrum M. The complexity of computing the sign of the Tutte polynomial Siam Journal On Computing. 43: 1921-1952. DOI: 10.1137/12088330X  0.436
2014 Cai JY, Galanis A, Goldberg LA, Guo H, Jerrum M, Štefankovič D, Vigoda E. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region Journal of Computer and System Sciences. DOI: 10.1016/J.Jcss.2015.11.009  0.412
2013 Bulatov AA, Dyer M, Goldberg LA, Jerrum M, McQuillan C. The expressibility of functions on the boolean domain, with applications to counting CSPs Journal of the Acm. 60. DOI: 10.1145/2528401  0.392
2013 Goldberg LA, Jerrum M. A polynomial-time algorithm for estimating the partition function of the ferromagnetic ising model on a regular matroid Siam Journal On Computing. 42: 1132-1157. DOI: 10.1137/110851213  0.402
2013 Goldberg LA, Jerrum M. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials Journal of Computer and System Sciences. 79: 68-78. DOI: 10.1016/J.Jcss.2012.04.005  0.461
2012 Goldberg LA, Jerrum M. A counterexample to rapid mixing of the Ge-Štefankovic process Electronic Communications in Probability. 17: 1-6. DOI: 10.1214/Ecp.V17-1712  0.504
2012 Goldberg LA, Jerrum M. Approximating the partition function of the ferromagnetic potts model Journal of the Acm. 59. DOI: 10.1145/2371656.2371660  0.436
2012 Bulatov A, Dyer M, Goldberg LA, Jalsenius M, Jerrum M, Richerby D. The complexity of weighted and unweighted #CSP Journal of Computer and System Sciences. 78: 681-688. DOI: 10.1016/J.Jcss.2011.12.002  0.332
2012 Goldberg LA, Jerrum M. Inapproximability of the Tutte polynomial of a planar graph Computational Complexity. 21: 605-642. DOI: 10.1007/S00037-012-0046-4  0.388
2012 Goldberg LA, Jerrum M. The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7391: 399-410. DOI: 10.1007/978-3-642-31594-7_34  0.335
2010 Jerrum M. Technical perspective constraint satisfaction problems and computational complexity Communications of the Acm. 53: 98. DOI: 10.1145/1810891.1810913  0.342
2010 Goldberg LA, Grohe M, Jerrum M, Thurley M. A complexity dichotomy for partition functions with mixed signs Siam Journal On Computing. 39: 3336-3402. DOI: 10.1137/090757496  0.471
2010 Dyer M, Goldberg LA, Jerrum M. An approximation trichotomy for Boolean #CSP Journal of Computer and System Sciences. 76: 267-277. DOI: 10.1016/J.Jcss.2009.08.003  0.44
2010 Dyer M, Goldberg LA, Jerrum M. A complexity dichotomy for hypergraph partition functions Computational Complexity. 19: 605-633. DOI: 10.1007/S00037-010-0300-6  0.377
2009 Dyer M, Goldberg LA, Jerrum M. Matrix norms and rapid mixing for Spin systems Annals of Applied Probability. 19: 71-107. DOI: 10.1214/08-Aap532  0.42
2008 Dyer M, Goldberg LA, Jerrum M. The complexity of weighted Boolean #CSP Siam Journal On Computing. 38: 1970-1986. DOI: 10.1137/070690201  0.364
2008 Dyer M, Goldberg LA, Jerrum M. Dobrushin conditions and systematic scan Combinatorics Probability and Computing. 17: 761-779. DOI: 10.1017/S0963548308009437  0.317
2008 Goldberg LA, Jerrum M. Inapproximability of the Tutte polynomial Information & Computation. 206: 908-929. DOI: 10.1016/J.Ic.2008.04.003  0.332
2007 Goldberg LA, Jerrum M. The complexity of ferromagnetic ising with local fields Combinatorics Probability and Computing. 16: 43-61. DOI: 10.1017/S096354830600767X  0.379
2006 Dyer M, Goldberg LA, Jerrum M, Martin R. Markov chain comparison Probability Surveys. 3: 89-111. DOI: 10.1214/154957806000000041  0.313
2006 Dyer M, Goldberg LA, Jerrum M. Systematic scan for sampling colorings Annals of Applied Probability. 16: 185-230. DOI: 10.1214/105051605000000683  0.426
2006 Cryan M, Dyer M, Goldberg LA, Jerrum M, Martin R. Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows Siam Journal On Computing. 36: 247-278. DOI: 10.1137/S0097539703434243  0.381
2006 Jerrum M. Two remarks concerning balanced matroids Combinatorica. 26: 733-742. DOI: 10.1007/S00493-006-0039-5  0.431
2006 Jerrum M. On the approximation of one Markov chain by another Probability Theory and Related Fields. 135: 1-14. DOI: 10.1007/S00440-005-0453-4  0.312
2004 Jerrum M, Sinclair A, Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries Journal of the Acm. 51: 671-697. DOI: 10.1145/1008731.1008738  0.618
2004 Goldberg LA, Jerrum M, Kannan S, Paterson M. A bound on the capacity of backoff and acknowledgment-based protocols Siam Journal On Computing. 33: 313-331. DOI: 10.1137/S0097539700381851  0.476
2004 Dyer M, Goldberg LA, Jerrum M. Counting and sampling H-colourings Information and Computation. 189: 1-16. DOI: 10.1016/J.Ic.2003.09.001  0.386
2003 Goldberg LA, Jerrum M, Paterson M. The Computational Complexity of Two-State Spin Systems Random Structures and Algorithms. 23: 133-154. DOI: 10.1002/Rsa.10090  0.544
2002 Dyer M, Frieze A, Jerrum M. On counting independent sets in sparse graphs Siam Journal On Computing. 31: 1527-1541. DOI: 10.1137/S0097539701383844  0.462
2002 Dyer M, Goldberg LA, Greenhill C, Istrate G, Jerrum M. Convergence of the iterated prisoner's dilemma game Combinatorics Probability and Computing. 11: 135-147. DOI: 10.1017/S096354830100503X  0.408
2002 Goldberg LA, Jerrum M. The 'Burnside process' converges slowly Combinatorics Probability and Computing. 11: 21-34. DOI: 10.1017/S096354830100493X  0.391
2002 Dyer M, Jerrum M, Vigoda E. Rapidly mixing markov chains for dismantleable constraint graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2483: 68-77. DOI: 10.1007/3-540-45726-7_6  0.345
2001 Dyer M, Goldberg LA, Greenhill C, Jerrum M, Mitzenmacher M. An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings Siam Journal On Computing. 30: 1962-1975. DOI: 10.1137/S0097539700372708  0.636
2001 Jerrum M, Sinclair A, Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 712-721.  0.319
2000 Goldberg LA, Jerrum M. Randomly sampling molecules Siam Journal On Computing. 29: 834-853. DOI: 10.1137/S0097539797318864  0.46
2000 Goldberg LA, Jerrum M. Counting Unlabelled Subtrees Of A Tree Is #P-Complete Lms Journal of Computation and Mathematics. 3: 117-124. DOI: 10.1112/S1461157000000243  0.34
2000 Dyer M, Goldberg LA, Greenhill C, Jerrum M. On the relative complexity of approximate counting problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1913: 108-119. DOI: 10.1007/S00453-003-1073-Y  0.402
1999 Bubley R, Dyer M, Greenhill C, Jerrum M. On approximately counting colorings of small degree graphs Siam Journal On Computing. 29: 387-400. DOI: 10.1137/S0097539798338175  0.472
1999 Dyer M, Frieze A, Jerrum M. Counting independent sets in sparse graphs Annual Symposium On Foundations of Computer Science - Proceedings. 210-217.  0.364
1998 Goldberg LA, Jerrum M, MacKenzie PD. An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks Siam Journal On Computing. 27: 1083-1098. DOI: 10.1137/S0097539794272569  0.377
1998 Dyer M, Frieze A, Jerrum M. Approximately Counting Hamilton Paths and Cycles in Dense Graphs Siam Journal On Computing. 27: 1262-1272. DOI: 10.1137/S009753979426112X  0.48
1998 Jerrum M, Sorkin GB. The Metropolis algorithm for graph bisection Discrete Applied Mathematics. 82: 155-175. DOI: 10.1016/S0166-218X(97)00133-9  0.433
1998 Bubley R, Dyer M, Jerrum M. An Elementary Analysis of a Procedure for Sampling Points in a Convex Body Random Structures and Algorithms. 12: 213-215. DOI: 10.1002/(Sici)1098-2418(199805)12:3<213::Aid-Rsa1>3.0.Co;2-Y  0.36
1997 Goldberg LA, Jerrum M, Leighton T, Rao S. Doubly logarithmic communication algorithms for optical-communication parallel computers Siam Journal On Computing. 26: 1100-1119. DOI: 10.1137/S0097539793259483  0.317
1997 Frieze A, Jerrum M. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION Algorithmica (New York). 18: 67-81. DOI: 10.1007/Bf02523688  0.429
1997 Gore V, Jerrum M, Kannan S, Sweedyk Z, Mahaney S. A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language Information and Computation. 134: 59-74. DOI: 10.1006/Inco.1997.2621  0.385
1996 Hirshfeld Y, Jerrum M, Moller F. A polynomial-time algorithm for deciding bisimulation equivalence of normed basic parallel processes Mathematical Structures in Computer Science. 6: 251-259. DOI: 10.1017/S0960129500000992  0.377
1996 Hirshfeld Y, Jerrum M, Moller F. A polynomial algorithm for deciding bisimilarity of normed context-free processes Theoretical Computer Science. 158: 143-159. DOI: 10.1016/0304-3975(95)00064-X  0.457
1996 Jerrum M, Vazirani U. A Mildly Exponential Approximation Algorithm for the Permanent Algorithmica (New York). 16: 392-401. DOI: 10.1007/Bf01940871  0.366
1996 Frieze A, Jerrum M, Molloy M, Robinson R, Wormald N. Generating and Counting Hamilton Cycles in Random Regular Graphs Journal of Algorithms. 21: 176-198. DOI: 10.1006/Jagm.1996.0042  0.414
1995 Goldberg PW, Jerrum MR. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers Machine Learning. 18: 131-148. DOI: 10.1023/A:1022847329178  0.308
1995 Frieze A, Jerrum M. An analysis of a Monte Carlo algorithm for estimating the permanent Combinatorica. 15: 67-83. DOI: 10.1007/Bf01294460  0.373
1995 Jerrum M. A very simple algorithm for estimating the number of k -colorings of a low-degree graph Random Structures and Algorithms. 7: 157-165. DOI: 10.1002/Rsa.3240070205  0.443
1994 Irving R, Jerrum MR. Three-dimensional statistical data security problems Siam Journal On Computing. 23: 170-184. DOI: 10.1137/S0097539790191010  0.37
1994 Jerrum M. Counting trees in a graph is #P-complete Information Processing Letters. 51: 111-116. DOI: 10.1016/0020-0190(94)00085-9  0.441
1994 Dyer M, Frieze A, Jerrum M. Approximately counting Hamilton cycles in dense graphs Proceedings of the Annual Acm Siam Symposium On Discrete Algorithms. 336-343.  0.383
1993 Jerrum M, Sinclair A. Polynomial-time approximation algorithms for the Ising model Siam Journal On Computing. 22: 1087-1116. DOI: 10.1137/0222066  0.593
1993 Jerrum M, Sinclair A. Polynomial-time approximation algorithms for the Ising model Siam Journal On Computing. 22: 1087-1116.  0.336
1993 Jerrum M, Sorkin GB. Simulated annealing for graph bisection Annual Symposium On Foundatons of Computer Science (Proceedings). 94-103.  0.317
1992 Jerrum M. Large Cliques Elude the Metropolis Process Random Structures and Algorithms. 3: 347-359. DOI: 10.1002/Rsa.3240030402  0.416
1990 Jerrum M, Sinclair A. Fast uniform generation of regular graphs Theoretical Computer Science. 73: 91-100. DOI: 10.1016/0304-3975(90)90164-D  0.641
1990 Jerrum M. Two-dimensional monomer-dimer systems are computationally intractable Journal of Statistical Physics. 59: 1087-1088. DOI: 10.1007/Bf01025864  0.381
1989 Jerrum M, Sinclair A. Approximating the permanent Siam Journal On Computing. 18: 1149-1178. DOI: 10.1137/0218077  0.628
1989 Sinclair A, Jerrum M. Approximate counting, uniform generation and rapidly mixing Markov chains Information and Computation. 82: 93-133. DOI: 10.1016/0890-5401(89)90067-9  0.652
1989 Jerrum M, Sinclair A. Approximating the permanent Siam Journal On Computing. 18: 1149-1178.  0.359
1988 Jerrum M, Sinclair A. Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved Proceedings of the Annual Acm Symposium On Theory of Computing. 235-244. DOI: 10.1145/62212.62234  0.428
1986 Jerrum MR, Valiant LG, Vazirani VV. Random generation of combinatorial structures from a uniform distribution Theoretical Computer Science. 43: 169-188. DOI: 10.1016/0304-3975(86)90174-X  0.68
1986 Jerrum M. A compact representation for permutation groups Journal of Algorithms. 7: 60-78. DOI: 10.1016/0196-6774(86)90038-6  0.378
1985 Jerrum MR. The complexity of finding minimum-length generator sequences Theoretical Computer Science. 36: 265-289. DOI: 10.1016/0304-3975(85)90047-7  0.419
1984 Jerrum MR, Skyum S. Families of Fixed Degree Graphs for Processor Interconnection Ieee Transactions On Computers. 190-194. DOI: 10.1109/TC.1984.1676410  0.32
1982 Jerrum M, Snir M. SOME EXACT COMPLEXITY RESULTS FOR STRAIGHT-LINE COMPUTATIONS OVER SEMIRINGS Journal of the Acm. 29: 874-897. DOI: 10.1145/322326.322341  0.401
Show low-probability matches.