Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Mark Jerrum
2010 – today
- 2013
[j53]Leslie Ann Goldberg, Mark Jerrum: Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. J. Comput. Syst. Sci. 79(1): 68-78 (2013)- [c39]Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby: The complexity of approximating conservative counting CSPs. STACS 2013: 148-159
- [i21]Leslie Ann Goldberg, Mark Jerrum: The Complexity of Approximately Counting Tree Homomorphisms. CoRR abs/1305.6306 (2013)
- [i20]Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran: Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 3(1): 47-66 (2013)
- 2012
- [j52]Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity 21(4): 605-642 (2012)
- [j51]Leslie Ann Goldberg, Mark Jerrum: Approximating the partition function of the ferromagnetic potts model. J. ACM 59(5): 25 (2012)
- [j50]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby: The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78(2): 681-688 (2012)
- [c38]Leslie Ann Goldberg, Mark Jerrum: The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). ICALP (1) 2012: 399-410
- [c37]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Log-supermodular functions, functional clones and counting CSPs. STACS 2012: 302-313
- [i19]Leslie Ann Goldberg, Mark Jerrum: The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation). CoRR abs/1202.0313 (2012)
- [i18]Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby: The complexity of approximating conservative counting CSPs. CoRR abs/1208.1783 (2012)
- [i17]Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan: Approximating the partition function of planar two-state spin systems. CoRR abs/1208.4987 (2012)
- 2011
- [c36]Leslie Ann Goldberg, Mark Jerrum: A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. ICALP (1) 2011: 521-532
- [i16]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Log-supermodular functions, functional clones and counting CSPs. CoRR abs/1108.5288 (2011)
- [i15]Leslie Ann Goldberg, Mark Jerrum: A Counterexample to rapid mixing of the Ge-Stefankovic Process. CoRR abs/1109.5242 (2011)
- 2010
- [j49]Mark Jerrum: Constraint satisfaction problems and computational complexity: technical persepctive. Commun. ACM 53(9): 98 (2010)
- [j48]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity 19(4): 605-633 (2010)
- [j47]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76(3-4): 267-277 (2010)
- [j46]Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 36(4): 464-476 (2010)
- [j45]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. SIAM J. Comput. 39(7): 3336-3402 (2010)
- [c35]Leslie Ann Goldberg, Mark Jerrum: Approximating the Partition Function of the Ferromagnetic Potts Model. ICALP (1) 2010: 396-407
- [i14]Leslie Ann Goldberg, Mark Jerrum: Approximating the partition function of the ferromagnetic Potts model. CoRR abs/1002.0986 (2010)
- [i13]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby: The complexity of weighted and unweighted #CSP. CoRR abs/1005.2678 (2010)
- [i12]Leslie Ann Goldberg, Mark Jerrum: Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. CoRR abs/1006.5234 (2010)
- [i11]Leslie Ann Goldberg, Mark Jerrum: A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. CoRR abs/1010.6231 (2010)
2000 – 2009
- 2009
- [j44]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean CSP. SIAM J. Comput. 38(5): 1970-1986 (2009)
- [c34]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS 2009: 493-504
- [i10]Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial of a planar graph. CoRR abs/0907.1724 (2009)
- 2008
- [j43]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. Combinatorics, Probability & Computing 17(6): 761-779 (2008)
- [j42]Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial. Inf. Comput. 206(7): 908-929 (2008)
- [i9]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A complexity dichotomy for partition functions with mixed signs. CoRR abs/0804.1932 (2008)
- [i8]Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The Mixing Time of Glauber Dynamics for Colouring Regular Trees. CoRR abs/0806.0921 (2008)
- [i7]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: A complexity dichotomy for hypergraph partition functions. CoRR abs/0811.0037 (2008)
- 2007
- [j41]Leslie Ann Goldberg, Mark Jerrum: The Complexity of Ferromagnetic Ising with Local Fields. Combinatorics, Probability & Computing 16(1): 43-61 (2007)
- [c33]
- [i6]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean #CSP. CoRR abs/0704.3683 (2007)
- [i5]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: An approximation trichotomy for Boolean #CSP. CoRR abs/0710.4272 (2007)
- [i4]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Matrix norms and rapid mixing for spin systems. CoRR abs/math/0702744 (2007)
- 2006
- [j40]
- [j39]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)
- [c32]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. APPROX-RANDOM 2006: 327-338
- [i3]Leslie Ann Goldberg, Mark Jerrum: Inapproximability of the Tutte polynomial. CoRR abs/cs/0605140 (2006)
- 2005
- [i2]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin conditions and Systematic Scan. Electronic Colloquium on Computational Complexity (ECCC)(075) (2005)
- 2004
- [j38]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and sampling H-colourings? Inf. Comput. 189(1): 1-16 (2004)
- [j37]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)
- [j36]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
- [j35]Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2003)
- [j34]Leslie Ann Goldberg, Mark Jerrum, Mike Paterson: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2): 133-154 (2003)
- 2002
- [j33]Leslie Ann Goldberg, Mark Jerrum: The "Burnside Process" Converges Slowly. Combinatorics, Probability & Computing 11(1): 21-34 (2002)
- [j32]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): 135-147 (2002)
- [j31]Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002)
- [c31]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
- [c30]Mark Jerrum, Jung-Bae Son: Spectral Gap and log-Sobolev Constant for Balanced Matroids. FOCS 2002: 721-
- [c29]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and Sampling H-Colourings. RANDOM 2002: 51-67
- [c28]Martin E. Dyer, Mark Jerrum, Eric Vigoda: Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. RANDOM 2002: 68-77
- 2001
- [c27]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
- [j30]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)
- [c26]Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: On the relative complexity of approximate counting problems. APPROX 2000: 108-119
- [c25]Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson: A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP 2000: 705-716
- [c24]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
- [i1]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)
1990 – 1999
- 1999
- [j29]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)
- [j28]Leslie Ann Goldberg, Mark Jerrum: Randomly Sampling Molecules. SIAM J. Comput. 29(3): 834-853 (1999)
- [c23]Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. FOCS 1999: 210-217
- [c22]Yoram Hirshfeld, Mark Jerrum: Bisimulation Equivanlence Is Decidable for Normed Process Algebra. ICALP 1999: 412-421
- 1998
- [j27]Mark Jerrum, Gregory B. Sorkin: The Metropolis Algorithm for Graph Bisection. Discrete Applied Mathematics 82(1-3): 155-175 (1998)
- [j26]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)
- [j25]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)
- [j24]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)
- [c21]
- 1997
- [j23]Alan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1): 67-81 (1997)
- [j22]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)
- [j21]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)
- [c20]
- [c19]
- 1996
- [j20]Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 16(4/5): 392-401 (1996)
- [j19]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)
- [j18]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)
- [j17]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)
- [c18]
- 1995
- [j16]Alan M. Frieze, Mark Jerrum: An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. Combinatorica 15(1): 67-83 (1995)
- [j15]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)
- [j14]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)
- [c17]Alan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. IPCO 1995: 1-13
- 1994
- [j13]Mark Jerrum: Simple Translation-Invariant Concepts Are Hard to Learn. Inf. Comput. 113(2): 300-311 (1994)
- [j12]
- [j11]Robert W. Irving, Mark Jerrum: Three-Dimensional Statistical Data Security Problems. SIAM J. Comput. 23(1): 170-184 (1994)
- [c16]Yoram Hirshfeld, Mark Jerrum, Faron Moller: A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes. FOCS 1994: 623-631
- [c15]Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994: 336-343
- [c14]Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie: An W(log log n) Lower Bound for Routing in Optical Networks. SPAA 1994: 147-156
- 1993
- [j10]Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for the Ising Model. SIAM J. Comput. 22(5): 1087-1116 (1993)
- [c13]Paul W. Goldberg, Mark Jerrum: Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. COLT 1993: 361-369
- [c12]
- [c11]Mark Jerrum: An analysis of a Monte Carlo algorithm for estimating the permanent. IPCO 1993: 171-182
- [c10]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
- 1992
- [j9]Mark Jerrum: Large Cliques Elude the Metropolis Process. Random Struct. Algorithms 3(4): 347-360 (1992)
- [c9]Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. FOCS 1992: 320-326
- 1990
- [j8]Mark Jerrum, Alistair Sinclair: Fast Uniform Generation of Regular Graphs. Theor. Comput. Sci. 73(1): 91-100 (1990)
- [c8]Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). ICALP 1990: 462-475
1980 – 1989
- 1989
- [j7]Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. Inf. Comput. 82(1): 93-133 (1989)
- [j6]Mark Jerrum, Alistair Sinclair: Approximating the Permanent. SIAM J. Comput. 18(6): 1149-1178 (1989)
- 1988
- [c7]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
- [c6]Shaodi Gao, Mark Jerrum, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling: On Continuous Homotopic One Layer Routing. Symposium on Computational Geometry 1988: 392-402
- [c5]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
- 1987
- [c4]Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. WG 1987: 134-148
- 1986
- [j5]
- [j4]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
- [j3]Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985)
- [c3]Mark Jerrum: Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). ICALP 1985: 290-299
- 1984
- [j2]Mark Jerrum, Sven Skyum: Families of Fixed Degree Graphs for Processor Interconnection. IEEE Trans. Computers 33(2): 190-194 (1984)
- [c2]Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract). ICALP 1984: 270-280
- 1982
- [j1]
- [c1]
Coauthor Index
[j53] [c39] [i21] [i20] [j52] [j51] [j50] [c38] [c37] [i19] [i18] [i17] [c36] [i16] [i15] [j48] [j47] [j46] [j45] [c35] [i14] [i13] [i12] [i11] [j44] [c34] [i10] [j43] [j42] [i9] [i8] [i7] [j41] [c33] [i6] [i5] [i4] [j39] [c32] [i3] [i2] [j38] [j36] [j35] [j34] [j33] [j32] [c31] [c29] [j30] [c26] [c25] [c24] [j28] [j25] [c21] [j21] [c20] [c14] [c10]
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-13 23:09 CEST by the dblp team