David Richerby
From Wikipedia, the free encyclopedia
| Domaines | algorithmique, informatique théorique, complexité des problèmes d'optimisation |
|---|---|
| Institutions | lecteur en Computer Science and Electrical Engineering, Université de l'Essex (depuis 1/10/2019) |
| Diplôme | Ph. D. à l'Université de Cambridge |
| Directeur de thèse | Anuj Dawar |
| Renommé pour | Classification de la complexité de comptage des problèmes de satisfaction de contraintes |
| Distinctions | Prix Gödel (2021), |
David Richerby est un mathématicien et information théoricien, spécialiste de la complexité des problèmes d'optimisation. Il est lecteur en Computer Science and Electrical Engineering à l'Université de l'Essex.
Il obtient un Ph. D. à l'université de Cambridge en 2003 (« Fixed-Point Logics with Choice ».) sous la direction de Anuj Dawar[1]. 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[2] avec Andrei Bulatov, Jin-Yi Cai, Xi Chen et Martin Dyer ; le prix distingue trois articles, dont : Martin Dyer et David Richerby, « An Effective Dichotomy for the Counting Constraint Satisfaction Problem », Society for Industrial & Applied Mathematics (SIAM), vol. 42, no 3, , p. 1245–1274 (DOI 10.1137/100811258)
