Publications available on-line

Jump to year: 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010.

• Complementary partial orders and rectangle packing
  Mark Jerrum
  Technical Report, University of Edinburgh, Department of Computer Science, 1985.
  CSR-190-85

• Approximating the Permanent
  Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing 18 (1989), 1149-1178.
  DOI 10.1137/0218077
• Polynomial-time approximation algorithms for the Ising model
  SIAM Journal on Computing 22 (1993), 1087-1116.
  DOI 10.1137/0222066
• Uniform sampling modulo a group of symmetries using Markov chain simulation
  Mark Jerrum
  LFCS report ECS-LFCS-93-272
  

• Three-dimensional statistical data security problems
  Robert W. Irving and Mark R. Jerrum, SIAM Journal on Computation 23 (1994), 170-184.
  DOI 10.1137/S0097539790191010
• 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 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 polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
  Yoram Hirshfeld, Mark Jerrum and Faron Moller, Mathematical Structures in Computer Science 6 (1996), 251-259.
  DOI 10.1017/S0960129500000992
• 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
  

• 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.
  Draft version.

• Doubly logarithmic communication algorithms for optical-communication parallel computers
  Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, and Satish Rao, SIAM Journal on Computing 26 (1997), 1100-1119.
  DOI 10.1137/S0097539793259483
• The Metropolis algorithm for graph bisection
  Mark Jerrum and Gregory B. Sorkin, Discrete Applied Mathematics 82 (1998), 155-175.
  DOI 10.1016/S0166-218X(97)00133-9
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
  Martin Dyer, Alan Frieze and Mark Jerrum, SIAM Journal on Compututing 27 (1998), 1262-1272.
  DOI 10.1137/S009753979426112X
• 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.

• Approximately counting Hamilton paths and cycles in dense graphs
  Martin Dyer, Alan Frieze, and Mark Jerrum, SIAM Journal on Computing 27 (1998), 1262-1272.
  DOI 10.1137/S009753979426112X
• An Omega(sqrt(log log n)) lower bound for routing in optical networks
  Leslie Ann Goldberg, Mark Jerrum, and Philip D. MacKenzie, SIAM Journal on Computing 27 (1998), 1083-1098.
  DOI 10.1137/S0097539794272569
• Bisimulation equivalence is decidable for normed Process Algebra
  Yoram Hirshfeld and Mark Jerrum,
  LFCS report ECS-LFCS-98-386
  

• The Swendsen-Wang process does not always mix rapidly
  Vivek K. Gore and Mark R. Jerrum, Journal of Statistical Physics 97 (1999), 67-86.
  DOI 10.1023/A:1004610900745
  An extended abstract appeared in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997.

On Approximately counting colorings of small degree graphs
Russ Bubley, Martin Dyer, Catherine Greenhill, and Mark Jerrum, SIAM Journal on Computing 29 (1999), 387-400.
DOI 10.1137/S0097539798338175

• Counting unlabelled subtrees of a tree is #P-complete
  Leslie Ann Goldberg and Mark Jerrum, LMS Journal of Computation and Mathematics, 3 (2000), 117--124.
  Abstract/Download in pdf.
• Randomly Sampling Molecules
  Leslie Ann Goldberg and Mark Jerrum, SIAM Journal on Computing 29 (2000), 834-853
  DOI 10.1137/S0097539797318864
  A preliminary version appeared in: Proceedings of the 8th ACM/SIAM Symposium on Discrete Algorithms (SODA), 1997.
• An extension of path coupling and its application to the Glauber dynamics for graph colorings
  Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum and Michael Mitzenmacher, SIAM Journal on Computing 30 (2001), 1962-1975.
  DOI 10.1137/S0097539700372708
  An extended abstract appeared in: Proceedings of the 11th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2000.
• 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.
  DOI 10.1017/S096354830100503X
• On counting independent sets in sparse graphs
  Martin Dyer, Alan Frieze and Mark Jerrum, SIAM Journal on Computing 31 (2002), 1527--1541.
  DOI 10.1137/S0097539701383844
  A preliminary version appeared in: 40th Annual IEEE Symposium on Foundations of Computer Science, 1999.
• 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.
  This material was refined and generalised, and appeared in Annals of Applied Probability 14 (2004); see below.
• The "Burnside process" converges slowly
  Leslie Ann Goldberg and Mark Jerrum, Combinatorics, Probability and Computing 11 (2002), 21-34.
  DOI 10.1017/S096354830100493X
• The computational complexity of two-state spin systems
  Leslie Ann Goldberg, Mark Jerrum and Mike Paterson, Random Structures and Algorithms 23 (2003), 133--154.
  DOI 10.1002/rsa.10090
• Lecture Notes from a Nachdiplomvorlesung at ETH-Zürich "Counting, sampling and integrating: algorithms and complexity"
  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.
  • Chapter 8 Inductive bounds, cubes, trees and matroids. Draft as at 09/09/04.
  • Chapter 9 Logarithmic Sobolev inequalities. Draft as at 21/02/05.
  • Bibliography.
  Chapters 1-7 published as: Mark Jerrum, Counting, Sampling and Integrating: algorithms and complexity, Lectures in Mathematics -- ETH Zürich, Birkhäuser, Basel, 2003.
• On the relative complexity of approximate counting problems
  Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum, Algorithmica 38 (2004), 471--500.
  DOI 10.1007/s00453-003-1073-y
  A preliminary version appeared in: Approximation Algorithms for Combinatorial Optimization, Springer LNCS 1913, 2000.
• A bound on the capacity of backoff and acknowledgement-based protocols
  Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan and Mike Paterson SIAM Journal on Computing 33 (2004), 313--331.
  DOI 10.1137/S0097539700381851
  A preliminary version appeared in: Proceedings of the 27th Colloquium on Automata, Languages and Programming, 2000.

• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
  Mark Jerrum, Alistair Sinclair and Eric Vigoda, Journal of the Association for Computing Machinery (JACM), Volume 51 (2004), 671--697.
  DOI 10.1145/1008731.1008738
  A preliminary version appeared in: Proceedings of the 33rd ACM Symposium on the Theory of Computing, 2001.
• Counting and sampling H-colourings
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Information and Computation 189 (2004), 1-16.
  DOI 10.1016/j.ic.2003.09.001
  A preliminary version appeared in: Proceedings of RANDOM'02.
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
  Mark Jerrum, Jung-Bae Son, Prasad Tetali and Eric Vigoda, Annals of Applied Probability 14 (2004), 1741--1765.
  DOI 10.1214/105051604000000639
• Rapidly mixing Markov chains for dismantleable constraint graphs
  Martin Dyer, Mark Jerrum and Eric Vigoda.
  DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63, AMS, 2004.
  A preliminary version appeared in in: Randomization and Approximation Techniques in Computer Science (Proceedings of RANDOM'02), Springer Lecture Notes in Computer Science 2483 (2002), 68-77.
  DOI 10.1007/3-540-45726-7_6
• On the approximation of one Markov chain by another
  Mark Jerrum, Probability Theory and Related Fields, 135 (2006), 1--14.
  DOI 10.1007/s00440-005-0453-4
• Two remarks concerning balanced matroids
  Mark Jerrum, Combinatorica 26, 2006, 733--742.
  DOI 10.1007/s00493-006-0039-5
• 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, SIAM Journal on Computing 36 (2006), 247--278.
  DOI 10.1137/S0097539703434243
  An extended abstract appeared in: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02).
• Systematic scan for sampling colourings
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Annals of Applied Probability 16 (2006), 185-230.
  DOI 10.1214/105051605000000683
• Markov chain comparison
  Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin, Probability Surveys 3 (2006), 89-111.
  Abstract and link to full text.
• The complexity of ferromagnetic Ising with local fields
  Leslie Ann Goldberg and Mark Jerrum, Combinatorics, Probability and Computing 16 (2007), 43-61.
  DOI 10.1017/S096354830600767X
• Approximating the Tutte polynomial
  Mark Jerrum, In Combinatorics and Probability: A Tribute to Dominic Welsh (edited by Geoffrey Grimmett and Colin McDiarmid), Oxford University Press, 2007.
  Draft.
• Dobrushin conditions and systematic scan
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Combinatorics, Probability and Computing 17 (2008), 761-779.
  DOI 10.1017/S0963548308009437
  A preliminary version appeared in: Proc. 10th International Workshop on Randomization and Computation (RANDOM).
• Inapproximability of the Tutte polynomial
  Leslie Ann Goldberg and Mark Jerrum, Information and Computation 206 (2008), 908-929.
  DOI 10.1016/j.ic.2008.04.003
  An extended abstract appeared in: Proceedings of ACM STOC 2007.
• A complexity dichotomy for partition functions with mixed signs
  Leslie Ann Goldberg, Martin Grohe, Mark Jerrum and Marc Thurley, April 2008.
  arXiv:0804.1932
  An extended abstract appeared in: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009).
  DOI 10.4230/LIPIcs.STACS.2009.1821
• The mixing time of Glauber dynamics for colouring regular trees
  Leslie Ann Goldberg, Mark Jerrum and Marek Karpinski, June 2008.
  arXiv:0806.0921.
• A complexity dichotomy for hypergraph partition functions
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, October 2008.
  arXiv:0811.0037.
• Matrix norms and rapid mixing for spin systems
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Annals of Applied Probability, 19 (2009), 71-107.
  DOI 10.1214/08-AAP532
  
• The complexity of weighted Boolean #CSP
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, SIAM Journal on Computing 38 (2009) 1970-1986.
  DOI 10.1137/070690201
• Inapproximability of the Tutte polynomial of a planar graph
  Leslie Ann Goldberg and Mark Jerrum, September 2009.
  arXiv:0907.1724
• An approximation trichotomy for Boolean #CSP
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Journal of Computer and System Sciences (2010).
  DOI 10.1016/j.jcss.2009.08.003
• Approximating the partition function of the ferromagnetic Potts model
  Leslie Ann Goldberg and Mark Jerrum, February 2010.
  arXiv:1002.0986