Publications available on-line

• Approximately counting Hamilton cycles in dense graphs
  Martin Dyer, Alan Frieze and Mark Jerrum
  LFCS report ECS-LFCS-93-259
  

• Simulated annealing for graph bisection
  Mark Jerrum and Gregory Sorkin
  LFCS report ECS-LFCS-93-260
  

• Uniform sampling modulo a group of symmetries using Markov chain simulation
  Mark Jerrum
  LFCS report ECS-LFCS-93-272
  

• A polynomial algorithm for deciding bisimilarity of normed context-free processes
  Yoram Hirshfeld, Mark Jerrum and Faron Moller
  LFCS report ECS-LFCS-94-286
  

• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
  Yoram Hirshfeld, Mark Jerrum and Faron Moller
  LFCS report ECS-LFCS-94-288
  

• A very simple algorithm for estimating the number of k-colourings of a low-degree graph
  Mark Jerrum
  LFCS report ECS-LFCS-94-290
  

• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
  Alan Frieze and Mark Jerrum
  LFCS report ECS-LFCS-94-292
  

• The computational complexity of counting
  Mark Jerrum
  LFCS report ECS-LFCS-94-296
  

• Generating and counting Hamilton cycles in random regular graphs
  Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson and Nicholas Wormald
  LFCS report ECS-LFCS-94-313
  

• Computational Pólya theory
  Mark Jerrum
  LFCS report ECS-LFCS-95-317
  

• A quasi-polynomial-time algorithm for sampling words from a context-free language
  Vivek Gore and Mark Jerrum
  LFCS report ECS-LFCS-95-326
  

• A new approach to polynomial-time generation of random points in convex bodies
  Russ Bubley, Martin Dyer and Mark Jerrum
  LFCS report ECS-LFCS-96-343
  

• Randomly sampling molecules
  Leslie Goldberg and Mark Jerrum
  Research Report CS-RR-306 Department of Computer Science, University of Warwick

• The Swendsen-Wang process does not always mix rapidly
  Vivek K. Gore and Mark R. Jerrum
  LFCS report ECS-LFCS-96-349
  

• The Markov chain Monte Carlo method: an approach to approximate counting and integration
  Mark Jerrum and Alistair Sinclair.
  In Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.), PWS, 1996. This book appears not to be available in Europe, so I am making a PostScript version of the chapter available here.

• Mathematical foundations of the Markov chain Monte Carlo method
  A draft of a chapter to appear in a volume connected with a summer school on Probabilistic Methods for Algorithmic Discrete Mathematics in Montpellier, August 1998.

• Bisimulation equivalence is decidable for normed Process Algebra
  Yoram Hirshfeld and Mark Jerrum,
  LFCS report ECS-LFCS-98-386
  

• The ``Burnside process'' converges slowly
  Leslie Ann Goldberg and Mark Jerrum
  LFCS report ECS-LFCS-98-387
  

• On counting independent sets in sparse graphs
  Martin Dyer, Alan Frieze and Mark Jerrum
  LFCS report ECS-LFCS-98-391
  A revised version will appear in SIAM Journal on Computing 31 (2002), 1527--1541.
• Counting unlabelled subtrees of a tree is #P-complete
  Leslie Ann Goldberg and Mark Jerrum
  LFCS report ECS-LFCS-99-417
  

• A bound on the capacity of backoff and acknowledgement-based protocols
  Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan and Mike Paterson
  Computer Science Research Report CS-RR-365 Department of Computer Science, University of Warwick.
  A revised version will appear in SIAM Journal on Computing 33 (2004), 313--331.

• On the relative complexity of approximate counting problems
  Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
  Computer Science Research Report CS-RR-370 Department of Computer Science, University of Warwick
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
  Mark Jerrum, Alistair Sinclair, Eric Vigoda
  ECCC Report TR00-079
  Revised version with a somewhat smoother proof and reduced running time.
• Lecture Notes from a recent Nachdiplomvorlesung at ETH-Zürich "Counting, sampling and integrating: algorithms and complexity" (draft, under construction)
  Mark Jerrum, with the assistance of several others.
  • Chapter 1 (with Zsuzsanna Lipták), Two good counting algorithms.
  • Chapter 2 (with Uli Wagner) #P-completeness.
  • Chapter 3 (with Uli Wagner) Sampling and counting.
  • Chapter 4 (???) Coupling and colourings.
  • Chapter 5 (with Michael Hoffmann and Bernd Gärtner) Canonical paths and matchings.
  • Chapter 6 (with Alex Below and Christoph Ambühl) Volume of a convex body.
  • Chapter 7 (with Samuele Pedroni) Inapproximability.
  • Bibliography.

• The computational complexity of two-state spin systems
  Leslie Ann Goldberg, Mark Jerrum and Mike Paterson,
  Computer Science Research Report CS-RR-386, Department of Computer Science, University of Warwick, UK, November 2001.
• An extension of path coupling and its application to the Glauber dynamics for graph colourings
  Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum and Michael Mitzenmacher,
  SIAM Journal on Computing 30 (2001), 1962--1975. PostScript.
• Rapidly mixing Markov chains for dismantleable constraint graphs
  Martin Dyer, Mark Jerrum and Eric Vigoda.
  To appear in a special volume in the DIMACS series of the AMS. PostScript.
• Convergence of the Iterated Prisoner's Dilemma game
  Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Gabriel Istrate and Mark Jerrum,
  Combinatorics, Probability and Computing 11 (2002), 135--147. PostScript.
• Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows
  Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin.
  (An extended abstract will appear in the Proceedings of FOCS'02.) PostScript.
• Counting and sampling H-colourings
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
  Proceedings of RANDOM'02. PostScript.
  Journal version in Information and Computation.
• Spectral gap and log-Sobolev constant for balanced matroids
  Mark Jerrum and Jung-Bae Son,
  Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), IEEE Computer Society Press, 2002, 721--729. PostScript.
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
  Mark Jerrum, Jung-Bae Son, Prasad Tetali and Eric Vigoda,
  Isaac Newton Institute Preprint NI03006-CMP.
• On the approximation of one Markov chain by another
  Mark Jerrum
  arxiv:math.PR/0312340.