Publications available online

Approximately counting Hamilton cycles in dense graphs
Martin Dyer, Alan Frieze and Mark Jerrum
LFCS report
ECSLFCS93259

Simulated annealing for graph bisection
Mark Jerrum and Gregory Sorkin
LFCS report
ECSLFCS93260

Uniform sampling modulo a group of symmetries
using Markov chain simulation
Mark Jerrum
LFCS report
ECSLFCS93272

A polynomial algorithm for deciding bisimilarity of normed
contextfree processes
Yoram Hirshfeld, Mark Jerrum and Faron Moller
LFCS report
ECSLFCS94286

A polynomialtime algorithm for deciding bisimulation equivalence
of normed Basic Parallel Processes
Yoram Hirshfeld, Mark Jerrum and Faron Moller
LFCS report
ECSLFCS94288

A very simple algorithm for estimating the number of
kcolourings of a lowdegree graph
Mark Jerrum
LFCS report
ECSLFCS94290

Improved approximation algorithms for MAX kCUT and MAX BISECTION
Alan Frieze and Mark Jerrum
LFCS report
ECSLFCS94292

The computational complexity of counting
Mark Jerrum
LFCS report
ECSLFCS94296

Generating and counting Hamilton cycles in random regular graphs
Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson and Nicholas Wormald
LFCS report
ECSLFCS94313

Computational Pólya theory
Mark Jerrum
LFCS report ECSLFCS95317
 A quasipolynomialtime algorithm for sampling words
from a contextfree language
Vivek Gore and Mark Jerrum
LFCS report ECSLFCS95326
 A new approach to polynomialtime generation
of random points in convex bodies
Russ Bubley, Martin Dyer and Mark Jerrum
LFCS report ECSLFCS96343
 Randomly sampling molecules
Leslie Goldberg and Mark Jerrum
Research Report CSRR306 Department of Computer Science,
University of Warwick
 The SwendsenWang process does not always mix rapidly
Vivek K. Gore and Mark R. Jerrum
LFCS report ECSLFCS96349
 The Markov chain Monte Carlo method:
an approach to approximate counting and integration
Mark Jerrum and Alistair Sinclair.
In Approximation Algorithms for NPhard 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 ECSLFCS98386
 The ``Burnside process'' converges slowly
Leslie Ann Goldberg and Mark Jerrum
LFCS report ECSLFCS98387
 On counting independent sets in sparse graphs
Martin Dyer, Alan Frieze and Mark Jerrum
LFCS report ECSLFCS98391
A revised version will appear in
SIAM Journal on Computing 31 (2002), 15271541.

Counting unlabelled subtrees of a tree is #Pcomplete
Leslie Ann Goldberg and Mark Jerrum
LFCS report ECSLFCS99417

A bound on the capacity of backoff and acknowledgementbased protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan and Mike Paterson
Computer
Science Research Report CSRR365
Department of Computer Science, University of Warwick.
A revised version will appear in
SIAM Journal on Computing 33 (2004), 313331.
 On the relative complexity of approximate counting problems
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
Computer
Science Research Report CSRR370
Department of Computer Science, University of Warwick
 A polynomialtime approximation algorithm
for the permanent of a matrix with
nonnegative entries
Mark Jerrum, Alistair Sinclair, Eric Vigoda
ECCC
Report TR00079
Revised version with a somewhat smoother
proof and reduced running time.
 Lecture Notes from a recent Nachdiplomvorlesung
at ETHZü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)
#Pcompleteness.
 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 twostate spin systems
Leslie Ann Goldberg, Mark Jerrum and Mike Paterson,
Computer
Science Research Report CSRR386, 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), 19621975.
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), 135147. 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 Hcolourings
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum,
Proceedings of RANDOM'02.
PostScript.
Journal version
in Information and Computation.
 Spectral gap and logSobolev constant for balanced matroids
Mark Jerrum and JungBae Son,
Proceedings of the 43rd IEEE Symposium on Foundations of Computer
Science (FOCS'02), IEEE Computer Society Press, 2002, 721729.
PostScript.
 Elementary bounds on Poincaré and logSobolev constants
for decomposable Markov chains
Mark Jerrum, JungBae Son, Prasad Tetali and Eric Vigoda,
Isaac Newton Institute Preprint
NI03006CMP.
 On the approximation of one Markov chain by another
Mark Jerrum
arxiv:math.PR/0312340.