www.wikidata.de-de.nina.az

Martin Dyer Martin E Dyer 16 Juli 1946 in Ryde Isle of Wight ist ein britischer Informatiker Inhaltsverzeichnis 1 Leben

Martin Dyer

Martin E. Dyer (* 16. Juli 1946 in Ryde, Isle of Wight) ist ein britischer Informatiker.

Leben Bearbeiten

Dyer studierte an der University of Leeds mit dem Bachelor-Abschluss 1967, erwarb seinen Master-Abschluss 1968 am Imperial College und wurde 1979 an der Universität Leeds bei Les G. Proll promoviert (Vertex Enumeration in Mathematical Programming - Methods and Applications). Er ist Professor an der University of Leeds.

Werk Bearbeiten

Er befasst sich mit theoretischer Informatik, diskreter Optimierung und Kombinatorik.

Anfang der 1980er Jahre fand er (unabhängig von Nimrod Megiddo) die ersten in der Zeit linearen Algorithmen für lineare Programmierung in niedriger Dimension mit bedeutenden Anwendungen in der Computer-Geometrie.

Mit Alan Frieze und Ravindran Kannan fand er 1991 einen Polynom-zeitlichen Algorithmus zur Berechnung der Volumina konvexer Körper in allen Dimensionen. Alle drei erhielten dafür den Fulkerson-Preis und die Arbeit wurde bei der Verleihung des Knuth-Preises an Kannan besonders hervorgehoben als eine der überhaupt herausragendsten Entwicklungen von Algorithmen. Die vorher bekannten Algorithmen zur Volumenberechnung wuchsen in der Zeit exponentiell mit der Dimension. Ihr Algorithmus verwendet Markow-Ketten-Monte-Carlo-Algorithmen (MCMC) und ist eine der frühesten und wichtigsten Anwendungen dieser Technik bei Näherungsalgorithmen. Er fand Eingang in viele Lehrbücher als Paradebeispiel eines Algorithmus, bei dem exakt nachweisbar ist, das die Verwendung probabilistischer Methoden (Randomisierung) zu einer schnelleren Lösung eines Problems führt.

Mit seinem Doktoranden Russ Bubley entwickelte er die Weg-Kopplungs-Technik (path coupling) zur Berechnung der Mischungszeit von Markow-Ketten. Die Methode ist wichtig für die Entwicklung von MCMC, eine der wichtigsten Techniken für Näherungsalgorithmen zum Beispiel bei Abzählproblemen, die auf der Simulation schnell mischender Markow-Ketten beruhen. Dyer selbst fand einige der schnellsten bekannten Algorithmen für solche Näherungen für Abzählprobleme (approximate counting) zum Beispiel aus statistischer Physik und Angewandter Statistik (statistische Tests von Hypothesen).

Er leistete auch wichtige Beiträge zur Komplexitätstheorie von Abzählproblemen und war führend in der Klassifikation solcher Probleme, zum Beispiel Constraint-Satisfaction-Problems (CSP) und Homormorphismen von Graphen (mit Catherine Greenhill). Mit Frieze und Mark Jerrum bewies er, dass das Abzählen unabhängiger Mengen in Graphen mit beschränktem Grad NP-schwer ist. Genauer bewiesen sie, dass falls der maximale Grad ist kein polynomzeitlicher probabilistischer Näherungsalgorithmus für das Abzählproblem existiert (außer man nimmt an RP=NP). Aus der Arbeit folgt auch, dass der MCMC Algorithmus wahrscheinlich schon für versagt.

Dyer und Frieze leisteten wichtige Beiträge zur probabilistischen Analyse von Algorithmen in kombinatorischer Optimierung.

Preise Bearbeiten

2013 erhielt er den EATCS-Award und 1991 den Fulkerson-Preis mit Frieze und Kannan. Für 2021 wurde ihm gemeinsam mit David Richerby ein Gödel-Preis zugesprochen für ihre Arbeit An Effective Dichotomy for the Counting Constraint Satisfaction Problem von 2010. Wie die anderen Empfänger des Gödel-Preises von 2021 wurden damit Arbeiten gewürdigt, die den Höhepunkt der Klassifikation von Abzählkomplexität von Constraint Satisfaction Problems (CSP) darstellen. Sie bewiesen zusammen einen umfassendes Komplexitäts-Dichotomie-Theorem für das CSP-artige Abzähprobleme, die als Verteilungsfunktion (partition function) ausdrückbar sind: alle diese Probleme sind entweder in Polynomzeit lösbar oder Sharp-P-schwer.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Mathematics Genealogy Project
  2. Dyer, Frieze, Kannan A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM, Band 38, 1991, S. 1–17
  3. Bubley, Dyer Path coupling: a technique for proving rapid mixing in Markov chains, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997, S. 223–231
  4. Mengen von Knoten des Graphen, bei denen jeweils keine zwei Elemente der Menge mit einer Kante verbunden sind
  5. Dyer, Frieze, Jerrum On counting independent sets in sparse graphs, SIAM J. Computing, 31, 2002, 1527–1541
  6. Dyer, Richerby, An Effective Dichotomy for the Counting Constraint Satisfaction Problem, Arxiv 2010
  7. Laudatio zum Gödel-Preis 2021
Personendaten
NAME Dyer, Martin
ALTERNATIVNAMEN Dyer, Martin E.
KURZBESCHREIBUNG britischer Informatiker
GEBURTSDATUM 16. Juli 1946
GEBURTSORT Ryde, Isle of Wight
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Martin E Dyer 16 Juli 1946 in Ryde Isle of Wight ist ein britischer Informatiker Inhaltsverzeichnis 1 Leben 2 Werk 3 Preise 4 Weblinks 5 EinzelnachweiseLeben BearbeitenDyer studierte an der University of Leeds mit dem Bachelor Abschluss 1967 erwarb seinen Master Abschluss 1968 am Imperial College und wurde 1979 an der Universitat Leeds bei Les G Proll promoviert Vertex Enumeration in Mathematical Programming Methods and Applications 1 Er ist Professor an der University of Leeds Werk BearbeitenEr befasst sich mit theoretischer Informatik diskreter Optimierung und Kombinatorik Anfang der 1980er Jahre fand er unabhangig von Nimrod Megiddo die ersten in der Zeit linearen Algorithmen fur lineare Programmierung in niedriger Dimension mit bedeutenden Anwendungen in der Computer Geometrie Mit Alan Frieze und Ravindran Kannan fand er 1991 einen Polynom zeitlichen Algorithmus zur Berechnung der Volumina konvexer Korper in allen Dimensionen 2 Alle drei erhielten dafur den Fulkerson Preis und die Arbeit wurde bei der Verleihung des Knuth Preises an Kannan besonders hervorgehoben als eine der uberhaupt herausragendsten Entwicklungen von Algorithmen Die vorher bekannten Algorithmen zur Volumenberechnung wuchsen in der Zeit exponentiell mit der Dimension Ihr Algorithmus verwendet Markow Ketten Monte Carlo Algorithmen MCMC und ist eine der fruhesten und wichtigsten Anwendungen dieser Technik bei Naherungsalgorithmen Er fand Eingang in viele Lehrbucher als Paradebeispiel eines Algorithmus bei dem exakt nachweisbar ist das die Verwendung probabilistischer Methoden Randomisierung zu einer schnelleren Losung eines Problems fuhrt Mit seinem Doktoranden Russ Bubley 3 entwickelte er die Weg Kopplungs Technik path coupling zur Berechnung der Mischungszeit von Markow Ketten Die Methode ist wichtig fur die Entwicklung von MCMC eine der wichtigsten Techniken fur Naherungsalgorithmen zum Beispiel bei Abzahlproblemen die auf der Simulation schnell mischender Markow Ketten beruhen Dyer selbst fand einige der schnellsten bekannten Algorithmen fur solche Naherungen fur Abzahlprobleme approximate counting zum Beispiel aus statistischer Physik und Angewandter Statistik statistische Tests von Hypothesen Er leistete auch wichtige Beitrage zur Komplexitatstheorie von Abzahlproblemen und war fuhrend in der Klassifikation solcher Probleme zum Beispiel Constraint Satisfaction Problems CSP und Homormorphismen von Graphen mit Catherine Greenhill Mit Frieze und Mark Jerrum bewies er dass das Abzahlen unabhangiger Mengen 4 in Graphen mit beschranktem Grad NP schwer ist 5 Genauer bewiesen sie dass falls der maximale Grad d 25 displaystyle d geq 25 nbsp ist kein polynomzeitlicher probabilistischer Naherungsalgorithmus fur das Abzahlproblem existiert ausser man nimmt an RP NP Aus der Arbeit folgt auch dass der MCMC Algorithmus wahrscheinlich schon fur d 6 displaystyle d geq 6 nbsp versagt Dyer und Frieze leisteten wichtige Beitrage zur probabilistischen Analyse von Algorithmen in kombinatorischer Optimierung Preise Bearbeiten2013 erhielt er den EATCS Award und 1991 den Fulkerson Preis mit Frieze und Kannan Fur 2021 wurde ihm gemeinsam mit David Richerby ein Godel Preis zugesprochen fur ihre Arbeit An Effective Dichotomy for the Counting Constraint Satisfaction Problem von 2010 6 Wie die anderen Empfanger des Godel Preises von 2021 wurden damit Arbeiten gewurdigt die den Hohepunkt der Klassifikation von Abzahlkomplexitat von Constraint Satisfaction Problems CSP darstellen Sie bewiesen zusammen einen umfassendes Komplexitats Dichotomie Theorem fur das CSP artige Abzahprobleme die als Verteilungsfunktion partition function ausdruckbar sind alle diese Probleme sind entweder in Polynomzeit losbar oder Sharp P schwer 7 Weblinks BearbeitenHomepage in Leeds Laudatio EATCS Award PDF 64 kB Einzelnachweise Bearbeiten Mathematics Genealogy Project Dyer Frieze Kannan A random polynomial time algorithm for approximating the volume of convex bodies Journal of the ACM Band 38 1991 S 1 17 Bubley Dyer Path coupling a technique for proving rapid mixing in Markov chains Proceedings of the 38th Annual Symposium on Foundations of Computer Science IEEE 1997 S 223 231 Mengen von Knoten des Graphen bei denen jeweils keine zwei Elemente der Menge mit einer Kante verbunden sind Dyer Frieze Jerrum On counting independent sets in sparse graphs SIAM J Computing 31 2002 1527 1541 Dyer Richerby An Effective Dichotomy for the Counting Constraint Satisfaction Problem Arxiv 2010 Laudatio zum Godel Preis 2021Normdaten Person GND 1079122311 lobid OGND AKS VIAF 291303093 Wikipedia Personensuche PersonendatenNAME Dyer MartinALTERNATIVNAMEN Dyer Martin E KURZBESCHREIBUNG britischer InformatikerGEBURTSDATUM 16 Juli 1946GEBURTSORT Ryde Isle of Wight Abgerufen von https de wikipedia org w index php title Martin Dyer amp oldid 224547173