Mark Jerrum
Encyclopedia
Mark Richard Jerrum is a British
computer scientist and computational theorist.
Jerrum received his Ph.D.
in computer science in 1981 from University of Edinburgh
under the supervision of Leslie Valiant
. He is professor of pure mathematics at Queen Mary, University of London
.
With his student Alistair Sinclair
, Jerrum investigated the mixing behaviour of Markov chain
s to construct approximation algorithms for counting problems such as the computing the permanent
, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the Gödel Prize
in 1996. A refinement of these methods led to a fully polynomial time randomised approximation algorithm for computing the permanent, for which Jerrum and his co-authors received the Fulkerson Prize
in 2006.
Great Britain
Great Britain or Britain is an island situated to the northwest of Continental Europe. It is the ninth largest island in the world, and the largest European island, as well as the largest of the British Isles...
computer scientist and computational theorist.
Jerrum received his Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
in computer science in 1981 from University of Edinburgh
University of Edinburgh
The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...
under the supervision of Leslie Valiant
Leslie Valiant
Leslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
. He is professor of pure mathematics at Queen Mary, University of London
Queen Mary, University of London
Queen Mary, University of London is a public research university located in London, United Kingdom and a constituent college of the federal University of London...
.
With his student Alistair Sinclair
Alistair Sinclair
Alistair Sinclair is a British computer scientist and computational theorist.Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh in 1988 under the supervision of Mark Jerrum...
, Jerrum investigated the mixing behaviour of Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
s to construct approximation algorithms for counting problems such as the computing the permanent
Computing the permanent
In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions....
, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 1996. A refinement of these methods led to a fully polynomial time randomised approximation algorithm for computing the permanent, for which Jerrum and his co-authors received the Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
in 2006.
Select publications
- Frieze, A., Jerrum, M., Molloy M., Robinson, R., & Wormald, N. (1996). Generating and counting Hamilton cycles in random regular graphs. Journal of Algorithms, 21, 176-198. Link to article
External links
- Mark Jerrum's homepage at Queen Mary, University of LondonQueen Mary, University of LondonQueen Mary, University of London is a public research university located in London, United Kingdom and a constituent college of the federal University of London...