Mark Jerrum

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)[1]. 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.[2]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). [3] Er untersuchte auch Näherungsalgorithmen für Abzählprobleme aus dem Ising-Modell[4], innerhalb der Polya´s Theorie von Abzählproblemen (wie denen von chemischen Verbindungen und Färbungen auf Graphen)[5] und für Hamiltonsche Wege in Zufalls-Graphen[6]

Schriften

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

Weblinks

Einzelnachweise

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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mark Jerrum — Mark Richard Jerrum is a British computer scientist and computational theorist. Jerrum received his Ph.D. in computer science in 1981 from University of Edinburgh under the supervision of Leslie Valiant.[1] He is professor of pure mathematics at… …   Wikipedia

  • Mark Jerrum — Mark Richard Jerrum Residencia  Reino Unido Nacionalidad Británico …   Wikipedia Español

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • Computing the permanent — In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined… …   Wikipedia

  • Géraud Sénizergues — est professeur d informatique à l Université de Bordeaux et membre du Laboratoire bordelais de recherche en informatique. Récipiendaire du Prix Gödel en 2002 pour avoir démontré la décidabilité de l égalité des langages reconnus par des automates …   Wikipédia en Français

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

  • Manindra Agrawal — (hindi : मणीन्द्र अग्रवाल) (20 mai 1966 à Allâhâbâd ) est un mathématicien indien et professeur à l Institut indien de technologie de Kanpur. C est un des auteurs du test de primalité AKS. Lien externe Page personnelle (en) …   Wikipédia en Français

  • Mario Szegedy — Márió Szegedy (23 octobre 1960 ) est un mathématicien et informaticien hongrois. Il est professeur à l université Rutgers et a obtenu son doctorat de l université de Chicago. Liens externes Page personnelle (en) Publications de Mario …   Wikipédia en Français

  • Peter Shor — Peter Williston Shor, né le 14 août 1959, est un mathématicien américain. Il est connu pour son travail sur le calcul quantique, en particulier pour l algorithme de Shor. Il est professeur au MIT et membre du CSAIL. En 1998, il reçoit le prix… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”