Mark Jerrum

Research interests

My main activities are in the part of theoretical computer science known as computational complexity. Within that area, I have particular interests in probabilistic computation, the complexity of combinatorial enumeration, information- and complexity-theoretic aspects of machine learning, and combinatorial optimisation. I dabble a little in related areas of mathematics such as combinatorics and the theory of stochastic processes. Very occasionally, I might flirt with Eurotheory.

Some publications are available online. Or, for a more nearly complete listing of publications, click here. (This listing is generated in real time by MathSciNet.)
"Algorithmically feasible sampling: what are the limits?", a presentation to a London Mathematical Society meeting, UCL, 7th October, 2005.
"Approximating the Tutte polynomial: a status report", a presentation to an OWL meeting "Combinatorics, probability and statistical mechanics", Oxford, 7 February 2006.

Some useful and not-so-useful links

Academic

ACM SIGACT (Special Interest Group on Algorithms and Computation Theory).
The British Combinatorial Bulletin.
A Compendium of NP-complete problems, courtesy of Pierluigi Crescenzi and Viggo Kann.
ElJC & WCE (The Electronic Journal of Combinatorics and World Combinatorics Exchange).
ESPRIT Thematic Network RAND-APX "Randomized and Approximation Algorithms".
ICMS (International Centre for Mathematical Sciences, Edinburgh)
e-MATH (AMS).
DIMACS (Center for Discrete Mathematics and Theoretical Computer Science, Rutgers Univ., NJ)
Matematisches Forschungsinstitut, Oberwolfach
Schloß Dagstuhl
Isaac Newton Institute, Cambridge
LMS
MCMC Preprint Service (MCMC = Markov chain Monte Carlo)
ECCC (Electronic Colloquium on Computational Complexity)
The Hypertext Bibliography Project
David Wilson's annotated bibliography of perfectly random sampling with Markov chains
Some mathematical constants

Information

UK railway timetable (Railtrack)
European railway timetable (Deutsche Bahn)
Airline timetable (Lufthansa)
The Train Line: On-line booking
GNER (with real-time arrival information)
Edinburgh Festival
BBC
Operabase
Internet Movie Database

Odds and ends

Generate your own Postmodern essay!
Hot! Live action from the construction site of the Milwaukee Art Museum.
The Trinity Footbridge
The Angel of the North
The Millennium Link (Forth & Clyde and Union Canals), including webcam of construction in progress at the site of the Falkirk Wheel.
The Tyne Bridge webcam (North tower) often gives a fine view of the splendid Gateshead Millennium Bridge.
Well that's the London Millennium Bridge easily trumped. Now...
Tate Modern eat your heart out! Here comes Baltic Centre for Contemporary Art.
An fine (if unfinished) Santiago Calatrava page, courtesy of Jeremy & Katie Kane.
Glass insulators (including link to porcelain insulator page)


Mark Jerrum
School of Informatics
University of Edinburgh
The King's Buildings
Edinburgh EH9 3JZ
United Kingdom

E-mail: mrj AT inf.ed.ac.uk