Mark Jerrum

from Wikipedia, the free encyclopedia

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

Jerrum received his PhD in 1981 from Leslie Valiant at the University of Edinburgh ( On the complexity of evaluating multivariate polynomials ). He was Professor in Edinburgh and 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. At the end of the 1980s, he and his student Alistair Sinclair , who received his doctorate with him in Edinburgh in 1988 , investigated the mixing properties of Markov chains and used them to construct Monte Carlo Markow chain approximation algorithms for counting problems such as matching and the related calculation of the permanent , a difficult problem, according to Valiant, within complexity theory. In 1996 they both received the Gödel Prize for this . In 2006, he and Alistair Sinclair and Eric Vigoda received the Fulkerson Prize for specifying a polynomial-time probabilistic approximation algorithm for calculating the permanence of a matrix with non-negative elements ( A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries , Journal of the ACM, Volume 51, 2004, pp. 671-697). He also examined approximation algorithms for counting problems from the Ising model , within Polya's theory of counting problems (such as those of chemical compounds and colorations on graphs) and for Hamiltonian paths in random graphs.

Fonts

  • Counting, sampling and integrating: algorithms and complexity , Birkhäuser 2003
  • with Sinclair The Markov chain Monte Carlo Method: an approach to approximate counting and integrating , in Dorit Hochbaum (Ed.) Approximate algorithms for NP hard problems , PWS Publishing 1997

Individual evidence

  1. ^ Mathematics Genealogy Project
  2. ↑ Jerrum, Sinclair Approximate counting, uniform generation and rapidly mixing Markov chains , Information and Computation, Volume 82, 1988, pp. 93-133, Jerrum, Sinclair Approximating the permanent , SIAM Journal on Computing, Volume 18, 1989, p. 1145 -1178
  3. ↑ Official site for the Fulkerson Prize
  4. ↑ Jerrum, Sinclair Polynomial time approximation algorithms for the Ising model , SIAM J. Computing, Volume 22, 1993, p. 1087
  5. ↑ Computational Polya theory , in Peter Rowlinson (Ed.) Surveys in Combinatorics, Stirling 1995 , London Math. Society Lecture Notes, Cambridge University Press, 1995, pp. 103-118
  6. ^ A. Frieze, Jerrum, M. Molloy, R. Robinson, N. Wormald Generating and counting Hamilton cycles in random regular graphs , Journal of Algorithms, Volume 21, 1996, pp. 176-198

Web links

personal data
SURNAME Jerrum, Mark
ALTERNATIVE NAMES Jerrum, Mark Richard
BRIEF DESCRIPTION British computer scientist
DATE OF BIRTH 1955