# Mark Jerrum

According to our database1, Mark Jerrum authored at least 162 papers between 1982 and 2018.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
Approximating Pairwise Correlations in the Ising Model.
CoRR, 2018

Approximately counting bases of bicircular matroids.
CoRR, 2018

Perfect simulation of the Hard Disks Model by Partial Rejection Sampling.
CoRR, 2018

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017
A Complexity Trichotomy for Approximately Counting List H-Colorings.
TOCT, 2017

Functional clones and expressibility of partition functions.
Theor. Comput. Sci., 2017

On the Switch Markov Chain for Perfect Matchings.
J. ACM, 2017

Computational Counting (Dagstuhl Seminar 18341).
Dagstuhl Reports, 2017

A simple FPRAS for bi-directed reachability.
CoRR, 2017

Random Walks on Small World Networks.
CoRR, 2017

The parameterised complexity of counting even and odd induced subgraphs.
Combinatorica, 2017

Uniform sampling through the Lovasz local lemma.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random cluster dynamics for the Ising model is rapidly mixing.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Counting Constraint Satisfaction Problems.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
The complexity of counting locally maximal satisfying assignments of Boolean CSPs.
Theor. Comput. Sci., 2016

Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard.
SIAM J. Comput., 2016

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.
J. Comput. Syst. Sci., 2016

Uniform Sampling through the Lovász Local Lemma.
CoRR, 2016

Random cluster dynamics for the Ising model is rapidly mixing.
CoRR, 2016

A complexity trichotomy for approximately counting list H-colourings.
CoRR, 2016

Functional Clones and Expressibility of Partition Functions.
CoRR, 2016

On the switch Markov chain for perfect matchings.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Complexity Trichotomy for Approximately Counting List H-Colourings.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Some Hard Families of Parameterized Counting Problems.
TOCT, 2015

The Complexity of Parity Graph Homomorphism: An Initial Investigation.
Theory of Computing, 2015

The parameterised complexity of counting connected subgraphs and graph motifs.
J. Comput. Syst. Sci., 2015

Approximating the partition function of planar two-state spin systems.
J. Comput. Syst. Sci., 2015

The complexity of approximating conservative counting CSPs.
J. Comput. Syst. Sci., 2015

The complexity of Boolean #MaximalCSP.
CoRR, 2015

Approximately Counting H-Colourings is #BIS-Hard.
CoRR, 2015

On the switch Markov chain for perfect matchings.
CoRR, 2015

Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
The Complexity of Approximately Counting Tree Homomorphisms.
TOCT, 2014

The Complexity of Computing the Sign of the Tutte Polynomial.
SIAM J. Comput., 2014

The parameterised complexity of counting even and odd induced subgraphs.
CoRR, 2014

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region.
Proceedings of the Approximation, 2014

2013
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.
SIAM J. Comput., 2013

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials.
J. Comput. Syst. Sci., 2013

The expressibility of functions on the boolean domain, with applications to counting CSPs.
J. ACM, 2013

Computational Counting (Dagstuhl Seminar 13031).
Dagstuhl Reports, 2013

The Complexity of Approximately Counting Tree Homomorphisms
CoRR, 2013

Some hard classes of parameterised counting problems.
CoRR, 2013

The Parameterised Complexity of Counting Connected Subgraphs.
CoRR, 2013

The complexity of parity graph homomorphism: an initial investigation.
CoRR, 2013

Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs.
CoRR, 2013

The complexity of approximating conservative counting CSPs.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
The complexity of weighted and unweighted #CSP.
J. Comput. Syst. Sci., 2012

Approximating the partition function of the ferromagnetic potts model.
J. ACM, 2012

Approximating the partition function of planar two-state spin systems
CoRR, 2012

The complexity of approximating conservative counting CSPs
CoRR, 2012

The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation)
CoRR, 2012

Inapproximability of the Tutte polynomial of a planar graph.
Computational Complexity, 2012

Log-supermodular functions, functional clones and counting CSPs.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation).
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
A Counterexample to rapid mixing of the Ge-Stefankovic Process
CoRR, 2011

Log-supermodular functions, functional clones and counting CSPs
CoRR, 2011

A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
A Complexity Dichotomy for Partition Functions with Mixed Signs.
SIAM J. Comput., 2010

The mixing time of Glauber dynamics for coloring regular trees.
Random Struct. Algorithms, 2010

An approximation trichotomy for Boolean #CSP.
J. Comput. Syst. Sci., 2010

A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
CoRR, 2010

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
CoRR, 2010

The complexity of weighted and unweighted #CSP
CoRR, 2010

Approximating the partition function of the ferromagnetic Potts model
CoRR, 2010

A Complexity Dichotomy For Hypergraph Partition Functions.
Computational Complexity, 2010

Constraint satisfaction problems and computational complexity: technical persepctive.
Commun. ACM, 2010

Approximating the Partition Function of the Ferromagnetic Potts Model.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

10481 Executive Summary - Computational Counting.
Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

10481 Abstracts Collection - Computational Counting.
Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

2009
The Complexity of Weighted Boolean #CSP.
SIAM J. Comput., 2009

Inapproximability of the Tutte polynomial of a planar graph
CoRR, 2009

A Complexity Dichotomy for Partition Functions with Mixed Signs.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008
Inapproximability of the Tutte polynomial.
Inf. Comput., 2008

Dobrushin Conditions and Systematic Scan.
Combinatorics, Probability & Computing, 2008

A complexity dichotomy for hypergraph partition functions
CoRR, 2008

The Mixing Time of Glauber Dynamics for Colouring Regular Trees
CoRR, 2008

A complexity dichotomy for partition functions with mixed signs
CoRR, 2008

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 11.05., 2008

2007
The Complexity of Ferromagnetic Ising with Local Fields.
Combinatorics, Probability & Computing, 2007

Matrix norms and rapid mixing for spin systems
CoRR, 2007

An approximation trichotomy for Boolean #CSP
CoRR, 2007

The Complexity of Weighted Boolean #CSP
CoRR, 2007

Inapproximability of the Tutte polynomial.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.
SIAM J. Comput., 2006

Inapproximability of the Tutte polynomial
CoRR, 2006

Two Remarks Concerning Balanced Matroids.
Combinatorica, 2006

Dobrushin Conditions and Systematic Scan.
Proceedings of the Approximation, 2006

2005
Dobrushin conditions and Systematic Scan
Electronic Colloquium on Computational Complexity (ECCC), 2005

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 15.05., 2005

2004
A bound on the capacity of backoff and acknowledgment-based protocols.
SIAM J. Comput., 2004

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
J. ACM, 2004

Counting and sampling H-colourings?
Inf. Comput., 2004

The Relative Complexity of Approximate Counting Problems.
Algorithmica, 2004

2003
The computational complexity of two-state spin systems.
Random Struct. Algorithms, 2003

2002
On Counting Independent Sets in Sparse Graphs.
SIAM J. Comput., 2002

The "Burnside Process" Converges Slowly.
Combinatorics, Probability & Computing, 2002

Convergence Of The Iterated Prisoner's Dilemma Game.
Combinatorics, Probability & Computing, 2002

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Counting and Sampling H-Colourings.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Spectral Gap and log-Sobolev Constant for Balanced Matroids.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.
Proceedings of the Graphs, 2001

2000
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.
SIAM J. Comput., 2000

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
Electronic Colloquium on Computational Complexity (ECCC), 2000

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

On the relative complexity of approximate counting problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Randomly Sampling Molecules.
SIAM J. Comput., 1999

On Approximately Counting Colorings of Small Degree Graphs.
SIAM J. Comput., 1999

Bisimulation Equivanlence Is Decidable for Normed Process Algebra.
Proceedings of the Automata, 1999

On Counting Independent Sets in Sparse Graphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks.
SIAM J. Comput., 1998

Approximately Counting Hamilton Paths and Cycles in Dense Graphs.
SIAM J. Comput., 1998

An elementary analysis of a procedure for sampling points in a convex body.
Random Struct. Algorithms, 1998

The Metropolis Algorithm for Graph Bisection.
Discrete Applied Mathematics, 1998

The "Burnside Process" Converges Slowly.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

1997
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.
SIAM J. Comput., 1997

A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language.
Inf. Comput., 1997

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.
Algorithmica, 1997

The Swendsen-Wang Process Does Not Always Mix Rapidly.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Randomly Sampling Molecules.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes.
Theor. Comput. Sci., 1996

A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes.
Mathematical Structures in Computer Science, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.
J. Algorithms, 1996

A Mildly Exponential Approximation Algorithm for the Permanent.
Algorithmica, 1996

Learning Linear Transformations.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph.
Random Struct. Algorithms, 1995

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.
Machine Learning, 1995

An Analysis of a Monte Carlo Algorithm for Estimating the Permanent.
Combinatorica, 1995

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

1994
Simple Translation-Invariant Concepts Are Hard to Learn
Inf. Comput., September, 1994

Three-Dimensional Statistical Data Security Problems.
SIAM J. Comput., 1994

Counting Trees in a Graph is #P-Complete.
Inf. Process. Lett., 1994

An W(log log n) Lower Bound for Routing in Optical Networks.
SPAA, 1994

Approximately Counting Hamilton Cycles in Dense Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Polynomial-Time Approximation Algorithms for the Ising Model.
SIAM J. Comput., 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.
SPAA, 1993

An analysis of a Monte Carlo algorithm for estimating the permanent.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Simulated Annealing for Graph Bisection
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Large Cliques Elude the Metropolis Process.
Random Struct. Algorithms, 1992

A Mildly Exponential Approximation Algorithm for the Permanent
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Uniform Sampling Modulo a Group of Symmetries Using Markov Chain Simulation.
Proceedings of the Expanding Graphs, 1992

1990
Fast Uniform Generation of Regular Graphs.
Theor. Comput. Sci., 1990

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains
Inf. Comput., July, 1989

Approximating the Permanent.
SIAM J. Comput., 1989

1988
Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

On Continuous Homotopic One Layer Routing.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Continuous Homotopic One Layer Routing.
Proceedings of the Computational Geometry and its Applications, 1988

1987
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains.
Proceedings of the Graph-Theoretic Concepts in Computer Science, International Workshop, 1987

1986
Random Generation of Combinatorial Structures from a Uniform Distribution.
Theor. Comput. Sci., 1986

A Compact Representation for Permutation Groups.
J. Algorithms, 1986

1985
The Complexity of Finding Minimum-Length Generator Sequences.
Theor. Comput. Sci., 1985

Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract).
Proceedings of the Automata, 1985

1984
Families of Fixed Degree Graphs for Processor Interconnection.
IEEE Trans. Computers, 1984

The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract).
Proceedings of the Automata, 1984

1982
Some Exact Complexity Results for Straight-Line Computations over Semirings.
J. ACM, 1982

A Compact Representation for Permutation Groups
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982