Some Exact Complexity Results for Straight-Line Computations over Semirings. - Mark Jerrum; Marc Snir (J. ACM, 1982)

The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract). - Mark Jerrum (ICALP, 1984)

Families of Fixed Degree Graphs for Processor Interconnection. - Mark Jerrum; Sven Skyum (IEEE Trans. Computers, 1984)

Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). - Mark Jerrum (ICALP, 1985)

The Complexity of Finding Minimum-Length Generator Sequences. - Mark Jerrum (Theor. Comput. Sci., 1985)

A Compact Representation for Permutation Groups. - Mark Jerrum (J. Algorithms, 1986)

Random Generation of Combinatorial Structures from a Uniform Distribution. - Mark Jerrum; Leslie G. Valiant; Vijay V. Vazirani (Theor. Comput. Sci., 1986)

On Continuous Homotopic One Layer Routing. - Shaodi Gao; Michael Kaufmann 001; Kurt Mehlhorn; Wolfgang Rülling; Christoph Storb; Mark Jerrum (Workshop on Computational Geometry, 1988)

On Continuous Homotopic One Layer Routing. - Shaodi Gao; Mark Jerrum; Michael Kaufmann 001; Kurt Mehlhorn; Wolfgang Rülling (SCG, 1988)

Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) - Mark Jerrum; Alistair Sinclair (STOC, 1988)

Approximating the Permanent. - Mark Jerrum; Alistair Sinclair (SIAM J. Comput., 1989)

Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains - Alistair Sinclair; Mark Jerrum (Inf. Comput., 1989)

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). - Mark Jerrum; Alistair Sinclair (ICALP, 1990)

Fast Uniform Generation of Regular Graphs. - Mark Jerrum; Alistair Sinclair (Theor. Comput. Sci., 1990)

Uniform Sampling Modulo a Group of Symmetries Using Markov Chain Simulation. - Mark Jerrum (Expanding Graphs, 1992)

Large Cliques Elude the Metropolis Process. - Mark Jerrum (Random Struct. Algorithms, 1992)

Simulated Annealing for Graph Bisection - Mark Jerrum; Gregory B. Sorkin (FOCS, 1993)

An analysis of a Monte Carlo algorithm for estimating the permanent. - Mark Jerrum (IPCO, 1993)

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer. - Leslie Ann Goldberg; Mark Jerrum; Frank Thomson Leighton; Satish Rao (SPAA, 1993)

Polynomial-Time Approximation Algorithms for the Ising Model. - Mark Jerrum; Alistair Sinclair (SIAM J. Comput., 1993)

A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes - Yoram Hirshfeld; Mark Jerrum; Faron Moller (FOCS, 1994)

Approximately Counting Hamilton Cycles in Dense Graphs. - Martin E. Dyer; Alan M. Frieze; Mark Jerrum (SODA, 1994)

An W(log log n) Lower Bound for Routing in Optical Networks. - Leslie Ann Goldberg; Mark Jerrum; Philip D. MacKenzie (SPAA, 1994)

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

Three-Dimensional Statistical Data Security Problems. - Robert W. Irving; Mark Jerrum (SIAM J. Comput., 1994)

Simple Translation-Invariant Concepts Are Hard to Learn - Mark Jerrum (Inf. Comput., 1994)

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. - Alan M. Frieze; Mark Jerrum (IPCO, 1995)

An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. - Alan M. Frieze; Mark Jerrum (Comb., 1995)

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. - Paul W. Goldberg; Mark Jerrum (Mach. Learn., 1995)

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

Learning Linear Transformations. - Alan M. Frieze; Mark Jerrum; Ravi Kannan (FOCS, 1996)

A Mildly Exponential Approximation Algorithm for the Permanent. - Mark Jerrum; Umesh V. Vazirani (Algorithmica, 1996)

Generating and Counting Hamilton Cycles in Random Regular Graphs. - Alan M. Frieze; Mark Jerrum; Michael Molloy 001; Robert W. Robinson; Nicholas C. Wormald (J. Algorithms, 1996)

A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes. - Yoram Hirshfeld; Mark Jerrum; Faron Moller (Math. Struct. Comput. Sci., 1996)

A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes. - Yoram Hirshfeld; Mark Jerrum; Faron Moller (Theor. Comput. Sci., 1996)

The Swendsen-Wang Process Does Not Always Mix Rapidly. - Vivek Gore; Mark Jerrum (STOC, 1997)

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. - Alan M. Frieze; Mark Jerrum (Algorithmica, 1997)

A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language. - Vivek Gore; Mark Jerrum; Sampath Kannan; Z. Sweedyk; Stephen R. Mahaney (Inf. Comput., 1997)

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. - Leslie Ann Goldberg; Mark Jerrum; Frank Thomson Leighton; Satish Rao (SIAM J. Comput., 1997)

The Metropolis Algorithm for Graph Bisection. - Mark Jerrum; Gregory B. Sorkin (Discret. Appl. Math., 1998)

An elementary analysis of a procedure for sampling points in a convex body. - Russ Bubley; Martin E. Dyer; Mark Jerrum (Random Struct. Algorithms, 1998)

Approximately Counting Hamilton Paths and Cycles in Dense Graphs. - Martin E. Dyer; Alan M. Frieze; Mark Jerrum (SIAM J. Comput., 1998)

An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks. - Leslie Ann Goldberg; Mark Jerrum; Philip D. MacKenzie (SIAM J. Comput., 1998)

Bisimulation Equivanlence Is Decidable for Normed Process Algebra. - Yoram Hirshfeld; Mark Jerrum (ICALP, 1999)

On Approximately Counting Colorings of Small Degree Graphs. - Russ Bubley; Martin E. Dyer; Catherine S. Greenhill; Mark Jerrum (SIAM J. Comput., 1999)

Randomly Sampling Molecules. - Leslie Ann Goldberg; Mark Jerrum (SIAM J. Comput., 1999)

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. - Leslie Ann Goldberg; Mark Jerrum; Sampath Kannan; Mike Paterson (ICALP, 2000)

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). - Martin E. Dyer; Leslie Ann Goldberg; Catherine S. Greenhill; Mark Jerrum; Michael Mitzenmacher (SODA, 2000)

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries - Mark Jerrum; Eric Vigoda (Electron. Colloquium Comput. Complex., 2000)

Counting Unlabelled Subtrees of a Tree is #P-complete. - Leslie Ann Goldberg; Mark Jerrum (LMS J. Comput. Math., 2000)

An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. - Martin E. Dyer; Leslie Ann Goldberg; Catherine S. Greenhill; Mark Jerrum; Michael Mitzenmacher (SIAM J. Comput., 2000)

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. - Mark Jerrum; Alistair Sinclair; Eric Vigoda (STOC, 2001)

Spectral Gap and log-Sobolev Constant for Balanced Matroids. - Mark Jerrum; Jung-Bae Son (FOCS, 2002)

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. - Martin E. Dyer; Mark Jerrum; Eric Vigoda (RANDOM, 2002)

Convergence Of The Iterated Prisoner's Dilemma Game. - Martin E. Dyer; Leslie Ann Goldberg; Catherine S. Greenhill; Gabriel Istrate; Mark Jerrum (Comb. Probab. Comput., 2002)

The "Burnside Process" Converges Slowly. - Leslie Ann Goldberg; Mark Jerrum (Comb. Probab. Comput., 2002)

On Counting Independent Sets in Sparse Graphs. - Martin E. Dyer; Alan M. Frieze; Mark Jerrum (SIAM J. Comput., 2002)

The computational complexity of two-state spin systems. - Leslie Ann Goldberg; Mark Jerrum; Mike Paterson (Random Struct. Algorithms, 2003)

The Relative Complexity of Approximate Counting Problems. - Martin E. Dyer; Leslie Ann Goldberg; Catherine S. Greenhill; Mark Jerrum (Algorithmica, 2004)

Counting and sampling H-colourings? - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (Inf. Comput., 2004)

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. - Mark Jerrum; Alistair Sinclair; Eric Vigoda (J. ACM, 2004)

A bound on the capacity of backoff and acknowledgment-based protocols. - Leslie Ann Goldberg; Mark Jerrum; Sampath Kannan; Mike Paterson (SIAM J. Comput., 2004)

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. - Martin E. Dyer; Mark Jerrum; Marek Karpinski (Design and Analysis of Randomized and Approximation Algorithms, 2005)

Dobrushin conditions and Systematic Scan - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (Electron. Colloquium Comput. Complex., 2005)

Two Remarks Concerning Balanced Matroids. - Mark Jerrum (Comb., 2006)

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. - Mary Cryan; Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum; Russell A. Martin (SIAM J. Comput., 2006)

Matrix norms and rapid mixing for spin systems - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (CoRR, 2007)

The Complexity of Ferromagnetic Ising with Local Fields. - Leslie Ann Goldberg; Mark Jerrum (Comb. Probab. Comput., 2007)

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. - Martin E. Dyer; Mark Jerrum; Marek Karpinski (Design and Analysis of Randomized and Approximation Algorithms, 2008)

The Mixing Time of Glauber Dynamics for Colouring Regular Trees - Leslie Ann Goldberg; Mark Jerrum; Marek Karpinski (CoRR, 2008)

Inapproximability of the Tutte polynomial. - Leslie Ann Goldberg; Mark Jerrum (Inf. Comput., 2008)

The Complexity of Weighted Boolean #CSP. - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (SIAM J. Comput., 2009)

10481 Abstracts Collection - Computational Counting. - Peter Bürgisser; Leslie Ann Goldberg; Mark Jerrum (Computational Counting, 2010)

10481 Executive Summary - Computational Counting. - Peter Bürgisser; Leslie Ann Goldberg; Mark Jerrum (Computational Counting, 2010)

Constraint satisfaction problems and computational complexity: technical persepctive. - Mark Jerrum (Commun. ACM, 2010)

A Complexity Dichotomy For Hypergraph Partition Functions. - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (Comput. Complex., 2010)

An approximation trichotomy for Boolean #CSP. - Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (J. Comput. Syst. Sci., 2010)

The mixing time of Glauber dynamics for coloring regular trees. - Leslie Ann Goldberg; Mark Jerrum; Marek Karpinski (Random Struct. Algorithms, 2010)

A Complexity Dichotomy for Partition Functions with Mixed Signs. - Leslie Ann Goldberg; Martin Grohe; Mark Jerrum; Marc Thurley (SIAM J. Comput., 2010)

A Counterexample to rapid mixing of the Ge-Stefankovic Process - Leslie Ann Goldberg; Mark Jerrum (CoRR, 2011)

The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). - Leslie Ann Goldberg; Mark Jerrum (ICALP (1), 2012)

Log-supermodular functions, functional clones and counting CSPs. - Andrei A. Bulatov; Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum (STACS, 2012)

Inapproximability of the Tutte polynomial of a planar graph. - Leslie Ann Goldberg; Mark Jerrum (Comput. Complex., 2012)

Approximating the partition function of the ferromagnetic potts model. - Leslie Ann Goldberg; Mark Jerrum (J. ACM, 2012)

The complexity of weighted and unweighted #CSP. - Andrei A. Bulatov; Martin E. Dyer; Leslie Ann Goldberg; Markus Jalsenius; Mark Jerrum; David Richerby (J. Comput. Syst. Sci., 2012)

Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. - Jin-Yi Cai; Leslie Ann Goldberg; Heng Guo 001; Mark Jerrum (CoRR, 2013)

The Parameterised Complexity of Counting Connected Subgraphs. - Mark Jerrum; Kitty Meeks (CoRR, 2013)

Some hard classes of parameterised counting problems. - Mark Jerrum; Kitty Meeks (CoRR, 2013)

Computational Counting (Dagstuhl Seminar 13031). - Peter Bürgisser; Leslie Ann Goldberg; Mark Jerrum; Pascal Koiran (Dagstuhl Reports, 2013)

The expressibility of functions on the boolean domain, with applications to counting CSPs. - Andrei A. Bulatov; Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum; Colin McQuillan (J. ACM, 2013)

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. - Leslie Ann Goldberg; Mark Jerrum (J. Comput. Syst. Sci., 2013)

A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. - Leslie Ann Goldberg; Mark Jerrum (SIAM J. Comput., 2013)

The Complexity of Computing the Sign of the Tutte Polynomial. - Leslie Ann Goldberg; Mark Jerrum (SIAM J. Comput., 2014)

The Complexity of Approximately Counting Tree Homomorphisms. - Leslie Ann Goldberg; Mark Jerrum (ACM Trans. Comput. Theory, 2014)

Approximately Counting H-Colourings is # mathrm BIS # BIS -Hard. - Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum (ICALP (1), 2015)

Approximately Counting H-Colourings is #BIS-Hard. - Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum (CoRR, 2015)

The complexity of Boolean #MaximalCSP. - Leslie Ann Goldberg; Mark Jerrum (CoRR, 2015)

The complexity of approximating conservative counting CSPs. - Xi Chen 001; Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum; Pinyan Lu; Colin McQuillan; David Richerby (J. Comput. Syst. Sci., 2015)

Approximating the partition function of planar two-state spin systems. - Leslie Ann Goldberg; Mark Jerrum; Colin McQuillan (J. Comput. Syst. Sci., 2015)

The parameterised complexity of counting connected subgraphs and graph motifs. - Mark Jerrum; Kitty Meeks (J. Comput. Syst. Sci., 2015)

A complexity classification of spin systems with an external field. - Leslie Ann Goldberg; Mark Jerrum (Proc. Natl. Acad. Sci. USA, 2015)

The Complexity of Parity Graph Homomorphism: An Initial Investigation. - John D. Faben; Mark Jerrum (Theory Comput., 2015)

Some Hard Families of Parameterized Counting Problems. - Mark Jerrum; Kitty Meeks (ACM Trans. Comput. Theory, 2015)

A Complexity Trichotomy for Approximately Counting List H-Colourings. - Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum (ICALP, 2016)

A complexity trichotomy for approximately counting list H-colourings. - Leslie Ann Goldberg; Mark Jerrum (CoRR, 2016)

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. - Jin-Yi Cai; Andreas Galanis; Leslie Ann Goldberg; Heng Guo 001; Mark Jerrum; Daniel Stefankovic; Eric Vigoda (J. Comput. Syst. Sci., 2016)

Approximately Counting H-Colorings is $ # mathrm{BIS}$-Hard. - Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum (SIAM J. Comput., 2016)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs. - Leslie Ann Goldberg; Mark Jerrum (Theor. Comput. Sci., 2016)

Counting Constraint Satisfaction Problems. - Mark Jerrum (The Constraint Satisfaction Problem, 2017)

Random cluster dynamics for the Ising model is rapidly mixing. - Heng Guo 001; Mark Jerrum (SODA, 2017)

The parameterised complexity of counting even and odd induced subgraphs. - Mark Jerrum; Kitty Meeks (Comb., 2017)

A simple FPRAS for bi-directed reachability. - Heng Guo 001; Mark Jerrum (CoRR, 2017)

Computational Counting (Dagstuhl Seminar 18341). - Ivona Bezáková; Leslie Ann Goldberg; Mark Jerrum (Dagstuhl Reports, 2017)

On the Switch Markov Chain for Perfect Matchings. - Martin E. Dyer; Mark Jerrum; Haiko Müller (J. ACM, 2017)

Functional clones and expressibility of partition functions. - Andrei Bulatov 001; Leslie Ann Goldberg; Mark Jerrum; David Richerby; Stanislav Zivný (Theor. Comput. Sci., 2017)

A Complexity Trichotomy for Approximately Counting List H-Colorings. - Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum (ACM Trans. Comput. Theory, 2017)

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. - Heng Guo 001; Mark Jerrum (ICALP, 2018)

Uniform Sampling Through the Lovász Local Lemma. - Heng Guo 001; Mark Jerrum; Jingcheng Liu 001 (J. ACM, 2019)

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. - Heng Guo 001; Mark Jerrum (SIAM J. Comput., 2019)

Approximating Pairwise Correlations in the Ising Model. - Leslie Ann Goldberg; Mark Jerrum (ACM Trans. Comput. Theory, 2019)

Random Walks on Small World Networks. - Martin E. Dyer; Andreas Galanis; Leslie Ann Goldberg; Mark Jerrum; Eric Vigoda (ACM Trans. Algorithms, 2020)

The Size of the Giant Joint Component in a Binomial Random Double Graph. - Mark Jerrum; Tamás Makai (Electron. J. Comb., 2021)

Counting vertices of integer polytopes defined by facets. - Heng Guo 001; Mark Jerrum (CoRR, 2021)

Fundamentals of Partial Rejection Sampling. - Mark Jerrum (CoRR, 2021)

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. - Martin E. Dyer; Marc Heinrich; Mark Jerrum; Haiko Müller (Comb. Probab. Comput., 2021)

Approximately counting bases of bicircular matroids. - Heng Guo 001; Mark Jerrum (Comb. Probab. Comput., 2021)

Counting Weighted Independent Sets beyond the Permanent. - Martin E. Dyer; Mark Jerrum; Haiko Müller; Kristina Vuskovic (SIAM J. Discret. Math., 2021)

A simple polynomial-time approximation algorithm for total variation distances between product distributions. - Weiming Feng 001; Heng Guo 001; Mark Jerrum; Jiaheng Wang 002 (CoRR, 2022)

Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing. - Konrad Anand; Mark Jerrum (SIAM J. Comput., 2022)

Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482). - Holger Dell; Mark Richard Jerrum; Haiko Müller; Konrad Anand; Marcus Pappik (Dagstuhl Reports, 2022)

Perfect Sampling of q-Spin Systems on ℤ2 via Weak Spatial Mixing. - Konrad Anand; Mark Jerrum (CoRR, 2023)

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. - Weiming Feng 001; Heng Guo 001; Mark Jerrum; Jiaheng Wang 002 (TheoretiCS, 2023)

Counting Vertices of Integral Polytopes Defined by Facets. - Heng Guo 001; Mark Jerrum (Discret. Comput. Geom., 2023)

Glauber dynamics for the hard-core model on bounded-degree H-free graphs. - Mark Jerrum (CoRR, 2024)

Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees. - Konrad Anand; Weiming Feng 001; Graham Freifeld; Heng Guo 001; Mark Jerrum; Jiaheng Wang 002 (SoCG, 2025)