Mark Richard Jerrum (born 1955) is a British computer scientist and computational theorist. Jerrum received his Ph.D. in computer science 'On the complexity of evaluating multivariate polynomials' in 1981 from

University of Edinburgh The University of Edinburgh (, ; abbreviated as ''Edin.'' in Post-nominal letters, post-nominals) is a Public university, public research university based in Edinburgh, Scotland. Founded by the City of Edinburgh Council, town council under th ...

under the supervision of

Leslie Valiant Leslie Gabriel Valiant (born 28 March 1949) is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Compute ...

. He is professor of

pure mathematics Pure mathematics is the study of mathematical concepts independently of any application outside mathematics. These concepts may originate in real-world concerns, and the results obtained may later turn out to be useful for practical applications ...

Queen Mary, University of London Queen Mary University of London (QMUL, or informally QM, and formerly Queen Mary and Westfield College) is a public research university in Mile End, East London, England. It is a member institution of the federal University of London. Today, ...

. With his student Alistair Sinclair, Jerrum investigated the mixing behaviour of

Markov chain In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...

s to construct

approximation algorithms In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

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 The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

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 The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

in 2006.2006 Fulkerson Prize citation
''Notices of the AMS'', December 2006, volume 53, number 11.

Personal life

Jerrum does not own a television, but has confessed to colleagues that he enjoys watching COPS,

WWE World Wrestling Entertainment (WWE) is an American professional wrestling promotion. It is owned and operated by TKO Group Holdings, a majority-owned subsidiary of Endeavor Group Holdings. A global integrated media and entertainment company, ...

and previously WCW. He does admit, however, that only the first season of COPS is good television.

References

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 Elsevier ( ) is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', '' Cell'', the ScienceDirect collection of electronic journals, '' Trends'', t ...

'', 21, 176–198.

External links

Mark Jerrum home page
at

* 1955 births Living people Alumni of the University of Edinburgh British computer scientists Theoretical computer scientists Academics of Queen Mary University of London Gödel Prize laureates {{UK-compu-bio-stub