David Richerby est un mathématicien et information théoricien britannique, spécialiste de la complexité des problèmes d'optimisation. Il est lecteur en Computer Science and Electrical Engineering à l'Université de l'Essex.
Parcours professionnel Il obtient un Ph. D. à l'université de Cambridge en 2003 (« Fixed-Point Logics with Choice ») sous la direction de Anuj Dawar.. Il est assistant de recherche à l'université d'Oxford jusqu'en , puis à l'université de l'Essex.
Recherche Ses domaines de recherche sont notamment : Algorithmique : Conception et analyse d'algorithmes pour résoudre des problèmes combinatoires discrets, problèmes de comptage, et algorithmes d'approximation. Théorie de la complexité informatique : il s'intéresse particulièrement aux théorèmes de dichotomie qui montrent qu'en fonction d'un certain paramètre, un problème peut être soit facile, soit difficile, sans cas intermédiaire. Problèmes de satisfaction de contraintes : il s'intéresse également aux variantes, comme les homomorphismes de graphes et les partitions de graphes. Processus stochastiques : en particulier le processus de Moran qui modélise la propagation aléatoire de mutations génétiques à travers des populations géographiquement structurées.
Prix et distinctions Il est lauréat du prix Gödel en 2021 avec Andrei Bulatov, Jin-Yi Cai, Xi Chen et Martin Dyer ; le prix distingue trois articles, dont :
Publications (sélection)
Notes et références
Liens externes Page personnelle de David Richerby
Catégorie:Informaticien britannique Catégorie:Personnalité en informatique théorique Catégorie:Lauréat du prix Gödel