| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Leslie Ann Goldberg, Mark Jerrum |
The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Log-supermodular functions, functional clones and counting CSPs. |
STACS |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Log-supermodular functions, functional clones and counting CSPs |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
A Counterexample to rapid mixing of the Ge-Stefankovic Process |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski |
The mixing time of Glauber dynamics for coloring regular trees. |
Random Struct. Algorithms |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
Constraint satisfaction problems and computational complexity: technical persepctive. |
Commun. ACM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
A Complexity Dichotomy For Hypergraph Partition Functions. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby |
The complexity of weighted and unweighted #CSP |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Approximating the partition function of the ferromagnetic Potts model |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
An approximation trichotomy for Boolean #CSP. |
J. Comput. Syst. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley |
A Complexity Dichotomy for Partition Functions with Mixed Signs. |
SIAM J. Comput. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Approximating the Partition Function of the Ferromagnetic Potts Model. |
ICALP |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Inapproximability of the Tutte polynomial of a planar graph |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
The Complexity of Weighted Boolean CSP. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley |
A Complexity Dichotomy for Partition Functions with Mixed Signs. |
STACS |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Inapproximability of the Tutte polynomial. |
Inf. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Dobrushin Conditions and Systematic Scan. |
Combinatorics, Probability & Computing |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley |
A complexity dichotomy for partition functions with mixed signs |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski |
The Mixing Time of Glauber Dynamics for Colouring Regular Trees |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
A complexity dichotomy for hypergraph partition functions |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
The Complexity of Ferromagnetic Ising with Local Fields. |
Combinatorics, Probability & Computing |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
The Complexity of Weighted Boolean #CSP |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Matrix norms and rapid mixing for spin systems |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
An approximation trichotomy for Boolean #CSP |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Inapproximability of the Tutte polynomial. |
STOC |
2007 |
DBLP DOI BibTeX RDF |
complexity, approximation, Tutte polynomial |
| 1 | Mark Jerrum |
Two Remarks Concerning Balanced Matroids. |
Combinatorica |
2006 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000): 05B35, 05A99, 51E10, 68Q17 |
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Inapproximability of the Tutte polynomial |
CoRR |
2006 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Dobrushin Conditions and Systematic Scan. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Dobrushin conditions and Systematic Scan |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Counting and sampling H-colourings? |
Inf. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Alistair Sinclair, Eric Vigoda |
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. |
J. ACM |
2004 |
DBLP DOI BibTeX RDF |
permanent of a matrix, rapidly mixing Markov chains, Markov chain Monte Carlo |
| 1 | Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson |
A bound on the capacity of backoff and acknowledgment-based protocols. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum |
The Relative Complexity of Approximate Counting Problems. |
Algorithmica |
2003 |
DBLP DOI BibTeX RDF |
Computational complexity, Approximate counting |
| 1 | Leslie Ann Goldberg, Mark Jerrum, Mike Paterson |
The computational complexity of two-state spin systems. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum |
Convergence Of The Iterated Prisoner's Dilemma Game. |
Combinatorics, Probability & Computing |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
The "Burnside Process" Converges Slowly. |
Combinatorics, Probability & Computing |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
On Counting Independent Sets in Sparse Graphs. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Mark Jerrum, Eric Vigoda |
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. |
RANDOM |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Counting and Sampling H-Colourings. |
RANDOM |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Jung-Bae Son |
Spectral Gap and log-Sobolev Constant for Balanced Matroids. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Alistair Sinclair, Eric Vigoda |
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. |
STOC |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | 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) |
2000 |
DBLP BibTeX RDF |
|
| 1 | 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. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson |
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. |
ICALP |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum |
On the relative complexity of approximate counting problems. |
APPROX |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Randomly Sampling Molecules. |
SIAM J. Comput. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum |
On Approximately Counting Colorings of Small Degree Graphs. |
SIAM J. Comput. |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Yoram Hirshfeld, Mark Jerrum |
Bisimulation Equivanlence Is Decidable for Normed Process Algebra. |
ICALP |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
On Counting Independent Sets in Sparse Graphs. |
FOCS |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Russ Bubley, Martin E. Dyer, Mark Jerrum |
An elementary analysis of a procedure for sampling points in a convex body. |
Random Struct. Algorithms |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Gregory B. Sorkin |
The Metropolis Algorithm for Graph Bisection. |
Discrete Applied Mathematics |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie |
An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
Approximately Counting Hamilton Paths and Cycles in Dense Graphs. |
SIAM J. Comput. |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
The "Burnside Process" Converges Slowly. |
RANDOM |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Mark Jerrum |
Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. |
Algorithmica |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao |
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. |
SIAM J. Comput. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum |
Randomly Sampling Molecules. |
SODA |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Vivek Gore, Mark Jerrum |
The Swendsen-Wang Process Does Not Always Mix Rapidly. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Yoram Hirshfeld, Mark Jerrum, Faron Moller |
A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes. |
Theor. Comput. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Yoram Hirshfeld, Mark Jerrum, Faron Moller |
A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes. |
Mathematical Structures in Computer Science |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Umesh V. Vazirani |
A Mildly Exponential Approximation Algorithm for the Permanent. |
Algorithmica |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Mark Jerrum, Michael Molloy, Robert W. Robinson, Nicholas C. Wormald |
Generating and Counting Hamilton Cycles in Random Regular Graphs. |
J. Algorithms |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Mark Jerrum, Ravi Kannan |
Learning Linear Transformations. |
FOCS |
1996 |
DBLP DOI BibTeX RDF |
Valiant's PAC model, arbitrarily oriented cube, distributed sample points, learning (artificial intelligence), learning, polynomial time algorithm, linear transformations |
| 1 | Paul W. Goldberg, Mark Jerrum |
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. |
Machine Learning |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. |
Random Struct. Algorithms |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Mark Jerrum |
An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. |
Combinatorica |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Mark Jerrum |
Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. |
IPCO |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
Counting Trees in a Graph is #P-Complete. |
Inf. Process. Lett. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
Simple Translation-Invariant Concepts Are Hard to Learn |
Inf. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Robert W. Irving, Mark Jerrum |
Three-Dimensional Statistical Data Security Problems. |
SIAM J. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
Approximately Counting Hamilton Cycles in Dense Graphs. |
SODA |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie |
An W(log log n) Lower Bound for Routing in Optical Networks. |
SPAA |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Yoram Hirshfeld, Mark Jerrum, Faron Moller |
A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes |
FOCS |
1994 |
DBLP DOI BibTeX RDF |
normed context-free processes, language equivalence, polynomial-time algorithm, decidability, equivalence, context-free grammars, bisimilarity |
| 1 | Mark Jerrum, Alistair Sinclair |
Polynomial-Time Approximation Algorithms for the Ising Model. |
SIAM J. Comput. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
An analysis of a Monte Carlo algorithm for estimating the permanent. |
IPCO |
1993 |
DBLP BibTeX RDF |
|
| 1 | Paul W. Goldberg, Mark Jerrum |
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. |
COLT |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Gregory B. Sorkin |
Simulated Annealing for Graph Bisection |
FOCS |
1993 |
DBLP DOI BibTeX RDF |
unique smallest bisection, simulated annealing, Metropolis algorithm, graph bisection |
| 1 | Mark Jerrum |
Large Cliques Elude the Metropolis Process. |
Random Struct. Algorithms |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Umesh V. Vazirani |
A Mildly Exponential Approximation Algorithm for the Permanent |
FOCS |
1992 |
DBLP DOI BibTeX RDF |
worst-case time complexity, matrix permanent, mildly exponential approximation algorithm, permanent |
| 1 | Mark Jerrum, Alistair Sinclair |
Fast Uniform Generation of Regular Graphs. |
Theor. Comput. Sci. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Alistair Sinclair |
Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). |
ICALP |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Alistair Sinclair, Mark Jerrum |
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains |
Inf. Comput. |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Alistair Sinclair |
Approximating the Permanent. |
SIAM J. Comput. |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Shaodi Gao, Mark Jerrum, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling |
On Continuous Homotopic One Layer Routing. |
Symposium on Computational Geometry |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Shaodi Gao, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling, Christoph Storb, Mark Jerrum |
On Continuous Homotopic One Layer Routing. |
Workshop on Computational Geometry |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Alistair Sinclair |
Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) |
STOC |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Alistair Sinclair, Mark Jerrum |
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. |
WG |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum, Leslie G. Valiant, Vijay V. Vazirani |
Random Generation of Combinatorial Structures from a Uniform Distribution. |
Theor. Comput. Sci. |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
A Compact Representation for Permutation Groups. |
J. Algorithms |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
The Complexity of Finding Minimum-Length Generator Sequences. |
Theor. Comput. Sci. |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Jerrum |
Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). |
ICALP |
1985 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")