Mark Richard Jerrum (born 1955) is a

British British may refer to: Peoples, culture, and language * British people, nationals or natives of the United Kingdom, British Overseas Territories, and Crown Dependencies. ** Britishness, the British identity and common culture * British English, ...

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 ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 1 ...

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 Comput ...

. 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 , mottoeng = With united powers , established = 1785 – The London Hospital Medical College1843 – St Bartholomew's Hospital Medical College1882 – Westfield College1887 – East London College/Queen Mary College , type = Public researc ...

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

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...

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 s ...

for counting problems such as the

computing the permanent In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined ...

, 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 Interes ...

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.

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'', th ...

'', 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