Mark Jerrum

Mark Richard Jerrum (* 1955) ist ein britischer Informatiker. Jerrum wurde 1981 bei Leslie Valiant an der University of Edinburgh promoviert (On the complexity of evaluating multivariate polynomials). Er war Professor in Edinburgh und ist Professor für Reine Mathematik am Queen Mary College der Universität London. Jerrum befasst sich mit Kombinatorik, Komplexitätstheorie und stochastischen Prozessen, insbesondere mit randomisierten Algorithmen und Mischungszeiten von Markow-Ketten in kombinatorischen und geometrischen Problemen. Ende der 1980er Jahre untersuchte er mit seinem Studenten Alistair Sinclair, der bei ihm 1988 in Edinburgh promoviert wurde, Mischungseigenschaften von Markow-Ketten und konstruierte damit Monte Carlo Markow-Ketten-Näherungsalgorithmen für Abzählprobleme wie der von Matchings und damit zusammenhängend der Berechnung der Permanente, einem nach Ergebnissen von Valiant innerhalb der Komplexitätstheorie schwierigen Problem. 1996 erhielten beide dafür den Gödel-Preis. 2006 erhielt er mit Alistair Sinclair und Eric Vigoda den Fulkerson-Preis für die Angabe eines polynomzeitlichen probabilistischen Näherungs-Algorithmus zur Berechnung der Permanente einer Matrix mit nicht negativen Elementen (A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, Band 51, 2004, S. 671–697). Er untersuchte auch Näherungsalgorithmen für Abzählprobleme aus dem Ising-Modell, innerhalb der Polyas Theorie von Abzählproblemen (wie denen von chemischen Verbindungen und Färbungen auf Graphen) und für Hamiltonsche Wege in Zufalls-Graphen.