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). 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.

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. 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).

Einzelnachweise

  1. ↑ David Richerby im Mathematics Genealogy Project (englisch)
  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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.