Alistair Sinclair

Alistair Sinclair (geboren 1960) ist ein britisch Informatiker und Computertheoretiker.

Sinclair erhielt seinen B.A. in Mathematik von St. Johns College, Cambridge 1979 und sein Ph.D. in Informatik von der Universität von Edinburgh im Jahr 1988 unter der Aufsicht von Mark Jerrum.[1]Er ist Professor an der Informatikabteilung der Informatik Universität von Kalifornien, Berkeley und hat Fakultätspositionen an der University of Edinburgh inne und besucht Positionen unter Dimacs und die Internationales Informatikinstitut in Berkeley.

Sinclairs Forschungsinteressen umfassen das Design und die Analyse von Randomisierte Algorithmen, rechnerische Anwendungen stochastischer Prozesse und nichtlinearer dynamischer Systeme, Monte -Carlo -Methoden in Statistische Physik und Kombinatorische Optimierung. Mit seinem Berater Mark Jerrum, Sinclair untersuchte das Mischverhalten von Markov -Ketten konstruieren Näherungsalgorithmen Für das Zählen von Problemen wie die Berechnung der Permanentenmit Anwendungen in verschiedenen Bereichen wie Matching-Algorithmen, geometrischen Algorithmen, mathematischer Programmierung, Statistik, physikalischer Anwendungen und dynamischer Systeme. Diese Arbeit war in der theoretischen Informatik stark einflussreich und wurde mit dem anerkannt Gödel -Preis in 1996.[2] Eine Verfeinerung dieser Methoden führte zu einem vollständig polynomialen Zeitalgorithmus zur Berechnung der Permanenten, für die Sinclair und seine Co-Autoren die erhalten haben Fulkerson -Preis in 2006.[3]

Sinclairs anfängliche Formen Teil des Namens des Namens GNRS -Vermutung Auf metrischen Einbettungen von Familien mit geringfügigen Graphen.

Verweise

  1. ^ John, Sinclair, Alistair (1988). "Randomisierte Algorithmen zum Zählen und Erzeugen kombinatorischer Strukturen". HDL:1842/11392. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  2. ^ "1996 Gödel Prize Citation". Archiviert von das Original am 2. April 2015. Abgerufen 14. Dezember 2011.
  3. ^ 2006 Fulkerson -Preiszitat, Mitteilungen des AMS, Dezember 2006, Band 53, Nummer 11
    - "Fulkerson -Preis" Rechenkomplexität. Abgerufen am 11. April 2017.