| 2009 |
|---|
| 87 | EE | Leslie Ann Goldberg,
Martin Grohe,
Mark Jerrum,
Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs.
STACS 2009: 493-504 |
| 86 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
The Complexity of Weighted Boolean CSP.
SIAM J. Comput. 38(5): 1970-1986 (2009) |
| 2008 |
|---|
| 85 | EE | Leslie Ann Goldberg,
Martin Grohe,
Mark Jerrum,
Marc Thurley:
A complexity dichotomy for partition functions with mixed signs
CoRR abs/0804.1932: (2008) |
| 84 | EE | Leslie Ann Goldberg,
Mark Jerrum,
Marek Karpinski:
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
CoRR abs/0806.0921: (2008) |
| 83 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
A complexity dichotomy for hypergraph partition functions
CoRR abs/0811.0037: (2008) |
| 82 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Dobrushin Conditions and Systematic Scan.
Combinatorics, Probability & Computing 17(6): 761-779 (2008) |
| 81 | EE | Leslie Ann Goldberg,
Mark Jerrum:
Inapproximability of the Tutte polynomial.
Inf. Comput. 206(7): 908-929 (2008) |
| 2007 |
|---|
| 80 | EE | Leslie Ann Goldberg,
Mark Jerrum:
Inapproximability of the Tutte polynomial.
STOC 2007: 459-468 |
| 79 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
The Complexity of Weighted Boolean #CSP
CoRR abs/0704.3683: (2007) |
| 78 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
An approximation trichotomy for Boolean #CSP
CoRR abs/0710.4272: (2007) |
| 77 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Matrix norms and rapid mixing for spin systems
CoRR abs/math/0702744: (2007) |
| 76 | EE | Leslie Ann Goldberg,
Mark Jerrum:
The Complexity of Ferromagnetic Ising with Local Fields.
Combinatorics, Probability & Computing 16(1): 43-61 (2007) |
| 2006 |
|---|
| 75 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Dobrushin Conditions and Systematic Scan.
APPROX-RANDOM 2006: 327-338 |
| 74 | EE | Leslie Ann Goldberg,
Mark Jerrum:
Inapproximability of the Tutte polynomial
CoRR abs/cs/0605140: (2006) |
| 73 | EE | Mark Jerrum:
Two Remarks Concerning Balanced Matroids.
Combinatorica 26(6): 733-742 (2006) |
| 72 | EE | 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 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Dobrushin conditions and Systematic Scan
Electronic Colloquium on Computational Complexity (ECCC)(075): (2005) |
| 2004 |
|---|
| 70 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Counting and sampling H-colourings?
Inf. Comput. 189(1): 1-16 (2004) |
| 69 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Mark Jerrum,
Jung-Bae Son:
Spectral Gap and log-Sobolev Constant for Balanced Matroids.
FOCS 2002: 721- |
| 63 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
Counting and Sampling H-Colourings.
RANDOM 2002: 51-67 |
| 62 | EE | 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 | EE | 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 | EE | 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 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Catherine S. Greenhill,
Mark Jerrum:
On the relative complexity of approximate counting problems.
APPROX 2000: 108-119 |
| 56 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Martin E. Dyer,
Alan M. Frieze,
Mark Jerrum:
On Counting Independent Sets in Sparse Graphs.
FOCS 1999: 210-217 |
| 51 | EE | 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 | EE | Leslie Ann Goldberg,
Mark Jerrum:
The "Burnside Process" Converges Slowly.
RANDOM 1998: 331-345 |
| 47 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Mark Jerrum,
Marc Snir:
Some Exact Complexity Results for Straight-Line Computations over Semirings.
J. ACM 29(3): 874-897 (1982) |
