Mark Jerrum

	2009
88		Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS 2009: 493-504
87		Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial of a planar graph CoRR abs/0907.1724: (2009)
86		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean CSP. SIAM J. Comput. 38(5): 1970-1986 (2009)
	2008
85		Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A complexity dichotomy for partition functions with mixed signs CoRR abs/0804.1932: (2008)
84		Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The Mixing Time of Glauber Dynamics for Colouring Regular Trees CoRR abs/0806.0921: (2008)
83		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: A complexity dichotomy for hypergraph partition functions CoRR abs/0811.0037: (2008)
82		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. Combinatorics, Probability & Computing 17(6): 761-779 (2008)
81		Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial. Inf. Comput. 206(7): 908-929 (2008)
	2007
80		Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial. STOC 2007: 459-468
79		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean #CSP CoRR abs/0704.3683: (2007)
78		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: An approximation trichotomy for Boolean #CSP CoRR abs/0710.4272: (2007)
77		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Matrix norms and rapid mixing for spin systems CoRR abs/math/0702744: (2007)
76		Leslie Ann Goldberg, Mark Jerrum: The Complexity of Ferromagnetic Ising with Local Fields. Combinatorics, Probability & Computing 16(1): 43-61 (2007)
	2006
75		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. APPROX-RANDOM 2006: 327-338
74		Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial CoRR abs/cs/0605140: (2006)
73		Mark Jerrum: Two Remarks Concerning Balanced Matroids. Combinatorica 26(6): 733-742 (2006)
72		Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. SIAM J. Comput. 36(1): 247-278 (2006)
	2005
71		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin conditions and Systematic Scan Electronic Colloquium on Computational Complexity (ECCC)(075): (2005)
	2004
70		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and sampling H-colourings? Inf. Comput. 189(1): 1-16 (2004)
69		Mark Jerrum, Alistair Sinclair, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4): 671-697 (2004)
68		Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson: A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. 33(2): 313-331 (2004)
	2003
67		Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2003)
66		Leslie Ann Goldberg, Mark Jerrum, Mike Paterson: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2): 133-154 (2003)
	2002
65		Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin: Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. FOCS 2002: 711-720
64		Mark Jerrum, Jung-Bae Son: Spectral Gap and log-Sobolev Constant for Balanced Matroids. FOCS 2002: 721-
63		Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and Sampling H-Colourings. RANDOM 2002: 51-67
62		Martin E. Dyer, Mark Jerrum, Eric Vigoda: Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. RANDOM 2002: 68-77
61		Leslie Ann Goldberg, Mark Jerrum: The "Burnside Process" Converges Slowly Combinatorics, Probability & Computing 11(1): (2002)
60		Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum: Convergence Of The Iterated Prisoner's Dilemma Game Combinatorics, Probability & Computing 11(2): (2002)
59		Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002)
	2001
58		Mark Jerrum, Alistair Sinclair, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC 2001: 712-721
	2000
57		Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: On the relative complexity of approximate counting problems. APPROX 2000: 108-119
56		Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson: A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP 2000: 705-716
55		Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). SODA 2000: 616-624
54		Mark Jerrum, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries Electronic Colloquium on Computational Complexity (ECCC) 7(79): (2000)
53		Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. SIAM J. Comput. 30(6): 1962-1975 (2000)
	1999
52		Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. FOCS 1999: 210-217
51		Yoram Hirshfeld, Mark Jerrum: Bisimulation Equivanlence Is Decidable for Normed Process Algebra. ICALP 1999: 412-421
50		Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum: On Approximately Counting Colorings of Small Degree Graphs. SIAM J. Comput. 29(2): 387-400 (1999)
49		Leslie Ann Goldberg, Mark Jerrum: Randomly Sampling Molecules. SIAM J. Comput. 29(3): 834-853 (1999)
	1998
48		Leslie Ann Goldberg, Mark Jerrum: The "Burnside Process" Converges Slowly. RANDOM 1998: 331-345
47		Mark Jerrum, Gregory B. Sorkin: The Metropolis Algorithm for Graph Bisection. Discrete Applied Mathematics 82(1-3): 155-175 (1998)
46		Russ Bubley, Martin E. Dyer, Mark Jerrum: An elementary analysis of a procedure for sampling points in a convex body. Random Struct. Algorithms 12(3): 213-235 (1998)
45		Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie: An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks. SIAM J. Comput. 27(4): 1083-1098 (1998)
44		Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM J. Comput. 27(5): 1262-1272 (1998)
	1997
43		Leslie Ann Goldberg, Mark Jerrum: Randomly Sampling Molecules. SODA 1997: 183-192
42		Vivek Gore, Mark Jerrum: The Swendsen-Wang Process Does Not Always Mix Rapidly. STOC 1997: 674-681
41		Alan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1): 67-81 (1997)
40		Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, Stephen R. Mahaney: A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language. Inf. Comput. 134(1): 59-74 (1997)
39		Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao: Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM J. Comput. 26(4): 1100-1119 (1997)
	1996
38		Alan M. Frieze, Mark Jerrum, Ravi Kannan: Learning Linear Transformations. FOCS 1996: 359-368
37		Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 16(4/5): 392-401 (1996)
36		Alan M. Frieze, Mark Jerrum, Michael Molloy, Robert W. Robinson, Nicholas C. Wormald: Generating and Counting Hamilton Cycles in Random Regular Graphs. J. Algorithms 21(1): 176-198 (1996)
35		Yoram Hirshfeld, Mark Jerrum, Faron Moller: A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes. Mathematical Structures in Computer Science 6(3): 251-259 (1996)
34		Yoram Hirshfeld, Mark Jerrum, Faron Moller: A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes. Theor. Comput. Sci. 158(1&2): 143-159 (1996)
	1995
33		Alan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. IPCO 1995: 1-13
32		Alan M. Frieze, Mark Jerrum: An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. Combinatorica 15(1): 67-83 (1995)
31		Paul W. Goldberg, Mark Jerrum: Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Machine Learning 18(2-3): 131-148 (1995)
30		Mark Jerrum: A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. Random Struct. Algorithms 7(2): 157-166 (1995)
	1994
29		Yoram Hirshfeld, Mark Jerrum, Faron Moller: A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes FOCS 1994: 623-631
28		Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994: 336-343
27		Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie: An W(log log n) Lower Bound for Routing in Optical Networks. SPAA 1994: 147-156
26		Mark Jerrum: Simple Translation-Invariant Concepts Are Hard to Learn Inf. Comput. 113(2): 300-311 (1994)
25		Mark Jerrum: Counting Trees in a Graph is #P-Complete. Inf. Process. Lett. 51(3): 111-116 (1994)
24		Robert W. Irving, Mark Jerrum: Three-Dimensional Statistical Data Security Problems. SIAM J. Comput. 23(1): 170-184 (1994)
	1993
23		Paul W. Goldberg, Mark Jerrum: Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. COLT 1993: 361-369
22		Mark Jerrum, Gregory B. Sorkin: Simulated Annealing for Graph Bisection FOCS 1993: 94-103
21		Mark Jerrum: An analysis of a Monte Carlo algorithm for estimating the permanent. IPCO 1993: 171-182
20		Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao: A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer. SPAA 1993: 300-309
19		Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for the Ising Model. SIAM J. Comput. 22(5): 1087-1116 (1993)
	1992
18		Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent FOCS 1992: 320-326
17		Mark Jerrum: Large Cliques Elude the Metropolis Process. Random Struct. Algorithms 3(4): 347-360 (1992)
	1990
16		Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). ICALP 1990: 462-475
15		Mark Jerrum, Alistair Sinclair: Fast Uniform Generation of Regular Graphs. Theor. Comput. Sci. 73(1): 91-100 (1990)
	1989
14		Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains Inf. Comput. 82(1): 93-133 (1989)
13		Mark Jerrum, Alistair Sinclair: Approximating the Permanent. SIAM J. Comput. 18(6): 1149-1178 (1989)
	1988
12		Mark Jerrum, Alistair Sinclair: Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) STOC 1988: 235-244
11		Shaodi Gao, Mark Jerrum, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling: On Continuous Homotopic One Layer Routing. Symposium on Computational Geometry 1988: 392-402
10		Shaodi Gao, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling, Christoph Storb, Mark Jerrum: On Continuous Homotopic One Layer Routing. Workshop on Computational Geometry 1988: 55-70
	1987
9		Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. WG 1987: 134-148
	1986
8		Mark Jerrum: A Compact Representation for Permutation Groups. J. Algorithms 7(1): 60-78 (1986)
7		Mark Jerrum, Leslie G. Valiant, Vijay V. Vazirani: Random Generation of Combinatorial Structures from a Uniform Distribution. Theor. Comput. Sci. 43: 169-188 (1986)
	1985
6		Mark Jerrum: Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). ICALP 1985: 290-299
5		Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985)
	1984
4		Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract). ICALP 1984: 270-280
3		Mark Jerrum, Sven Skyum: Families of Fixed Degree Graphs for Processor Interconnection. IEEE Trans. Computers 33(2): 190-194 (1984)
	1982
2		Mark Jerrum: A Compact Representation for Permutation Groups FOCS 1982: 126-133
1		Mark Jerrum, Marc Snir: Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM 29(3): 874-897 (1982)

Coauthor Index

1	Russ Bubley	[46] [50]
2	Mary Cryan	[65] [72]
3	Martin E. Dyer	[28] [44] [46] [50] [52] [53] [55] [57] [59] [60] [62] [63] [65] [67] [70] [71] [72] [75] [77] [78] [79] [82] [83] [86]
4	Alan M. Frieze	[28] [32] [33] [36] [38] [41] [44] [52] [59]
5	Shaodi Gao	[10] [11]
6	Leslie Ann Goldberg	[20] [27] [39] [43] [45] [48] [49] [53] [55] [56] [57] [60] [61] [63] [65] [66] [67] [68] [70] [71] [72] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]
7	Paul W. Goldberg	[23] [31]
8	Vivek Gore	[40] [42]
9	Catherine S. Greenhill	[50] [53] [55] [57] [60] [67]
10	Martin Grohe	[85] [88]
11	Yoram Hirshfeld	[29] [34] [35] [51]
12	Robert W. Irving	[24]
13	Gabriel Istrate	[60]
14	Ravi Kannan (Ravindran Kannan)	[38]
15	Sampath Kannan	[40] [56] [68]
16	Marek Karpinski	[84]
17	Michael Kaufmann	[10] [11]
18	Frank Thomson Leighton (Tom Leighton)	[20] [39]
19	Philip D. MacKenzie	[27] [45]
20	Stephen R. Mahaney	[40]
21	Russell A. Martin	[65] [72]
22	Kurt Mehlhorn	[10] [11]
23	Michael Mitzenmacher	[53] [55]
24	Faron Moller	[29] [34] [35]
25	Michael Molloy (Michael S. O. Molloy)	[36]
26	Mike Paterson	[56] [66] [68]
27	Satish Rao	[20] [39]
28	Robert W. Robinson	[36]
29	Wolfgang Rülling	[10] [11]
30	Alistair Sinclair	[9] [12] [13] [14] [15] [16] [19] [58] [69]
31	Sven Skyum	[3]
32	Marc Snir	[1]
33	Jung-Bae Son	[64]
34	Gregory B. Sorkin	[22] [47]
35	Christoph Storb	[10]
36	Z. Sweedyk	[40]
37	Marc Thurley	[85] [88]
38	Leslie G. Valiant	[7]
39	Umesh V. Vazirani	[18] [37]
40	Vijay V. Vazirani	[7]
41	Eric Vigoda	[54] [58] [62] [69]
42	Nicholas C. Wormald	[36]

Colors in the list of coauthors