David Richerby

David Richerby ist ein britischer Informatiker und Mathematiker und Hochschullehrer an der University of Essex.

2003 wurde Richerby an der Universität Cambridge in Informatik bei Anuj Dawar promoviert (Fixed-point logics with choice).[1] Er ist seit 2019 Lecturer an der School of Computer Science and Electrical Engineering (CSEE) der University of Essex.

Er befasst sich mit dem SAT-Problem und anderen Constraint Satisfaction Problems (CSP) wie solche vom Abzähltyp, Komplexitätstheorie, Kombinatorik (und kombinatorischen Algorithmen), und stochastischen Prozessen wie dem Moran-Prozess, der die zufällige Ausbreitung von Mutationen in der Populationsgenetik mit geographisch strukturierten Populationen beschreibt.[2][3]

Für 2021 wurde ihm gemeinsam mit Martin Dyer ein Gödel-Preis zugesprochen für ihre Arbeit An Effective Dichotomy for the Counting Constraint Satisfaction Problem von 2010.[4][5] 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ählprobleme, die als Verteilungsfunktion (partition function) ausdrückbar sind: alle diese Probleme sind entweder in Polynomzeit lösbar oder Sharp-P-schwer (Laudatio zum Gödel-Preis).

Weblinks

• Webseite an der University of Essex
• Google Scholar
• David M. Richerby in der Datenbank zbMATH

Einzelnachweise

1. David Richerby im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
2. L. Goldberg, J. Lapinskas, D. Richerby, Phase transitions of the Moran process and algorithmic consequences, Random Structures and Algorithms, Band 56, 2020, S. 597–647
3. J. Diaz,L.A. Goldberg, G. B. Mertzios, D. Richerby, M. Serna, P. G. Spirakis, Approximating fixation probabilities in the generalized Moran process, Algorithmica, Band 69, 2014, S. 78–91
4. Dyer, Richerby, An Effective Dichotomy for the Counting Constraint Satisfaction Problem, Arxiv 2010
5. Gödel Prize 2021