| 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 | |
| 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) | |
| 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) | |
| 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 | |
| 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 | ||
Colors in the list of coauthors
Last update Sat May 25 08:34:14 2013 CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page