Martin Dyer

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)[1]. Er ist Professor an der University of Leeds.

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 Approximation der Volumina konvexer Körper in allen Dimensionen[2]. 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[3] 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[4] in Graphen mit beschränktem Grad NP-schwer ist[5]. Genauer bewiesen sie, dass falls der maximale Grad ${\displaystyle d\geq 25}$ 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 ${\displaystyle d\geq 6}$ versagt.

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

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.[6] 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.[7]

• Homepage in Leeds
• Laudatio EATCS Award (PDF; 64 kB)

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