David Richerby
| 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.
Parcours professionnel[modifier | modifier le code]
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 août 2019, puis à l'université de l'Essex.
Recherche[modifier | modifier le code]
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[modifier | modifier le code]
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)
Publications (sélection)[modifier | modifier le code]
- Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas et Dvid Richerby, « Amplifiers for the Moran Process », Journal of the ACM, vol. 64, no 1, , p. 5:1–5:90 (DOI 10.1145/3019609)
- Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum et David Richerby, « Functional clones and expressibility of partition functions », Theoretical Computer Science, vol. 687, , p. 11–39 (DOI 10.1016/j.tcs.2017.05.001, arXiv 1609.07377)
- Till Blume, David Richerby et Ansgar Scherp, « FLUID: A common model for semantic structural graph summaries based on equivalence relations », Theoretical Computer Science, vol. 854, , p. 136–158 (DOI 10.1016/j.tcs.2020.12.019, arXiv 1908.01528)
- Leslie Ann Goldberg, John Lapinskas et David Richerby, « Faster exponential-time algorithms for approximately counting independent sets », Theoretical Computer Science, vol. 892, , p. 48–84 (DOI 10.1016/j.tcs.2021.09.009, arXiv 2005.05070)
- Leslie Ann Goldberg, John Lapinskas et David Richerby, « Phase transitions of the Moran process and algorithmic consequences », Random Structures & Algorithms, vol. 56, no 3, , p. 597–647 (DOI 10.1002/rsa.20890, arXiv 1804.02293)
Notes et références[modifier | modifier le code]
- (en) « David Richerby », sur le site du Mathematics Genealogy Project.
- « 2021 Gödel Prize citation »
Liens externes[modifier | modifier le code]
- Ressources relatives à la recherche :
