Mark Jerrum

Mark Jerrum Richard ( born 1955 ) is a British computer scientist.

Jerrum in 1981 at Leslie Valiant at the University of Edinburgh PhD ( On the complexity of multivariate polynomials Evaluating ). He was a professor in Edinburgh and is a Professor of Pure Mathematics at Queen Mary College, University of London.

Jerrum deals with combinatorics, complexity theory and stochastic processes, in particular with randomized algorithms and mixing times of Markov chains in combinatorial and geometric problems. In the late 1980s, he and his student Alistair Sinclair, who received his doctorate in Edinburgh with him in 1988, mixing properties of Markov chains and thus constructed Monte Carlo Markov chain approximation algorithms for counting problems such as that of matching and related to the calculation of the Permanente according to results of a Valiant difficult within the complexity theory Problem.1996 received both for the Gödel prize. In 2006 he was awarded with Alistair Sinclair and Eric Vigoda the Fulkerson Prize for specifying a polynomzeitlichen probabilistic approximation algorithm for computing the permanent of a matrix with non-negative elements (A polynomial - time approximation algorithm for the permanent of a matrix with Nonnegative entries, journal of the ACM, Volume 51, 2004, pp. 671-697 ). He also studied approximate algorithms for counting problems from the Ising model, within the Polya 's theory of Abzählproblemen ( such as those of chemical compounds and colorings on graphs ) and for Hamiltonian paths in random graphs

Writings

• Counting, sampling and integra ting: algorithms and complexity, Birkhauser 2003
• With Markov chain Monte Carlo The Sinclair Method: an approach to approximate counting and integra ting, in Dorit Hochbaum (ed.) Approximate algorithms for NP hard problems, PWS Publishing, 1997