David Richerby

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

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

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, n^o 3,‎ 2013, p. 1245–1274 (DOI 10.1137/100811258)

Publications (sélection)

• Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas et Dvid Richerby, « Amplifiers for the Moran Process », Journal of the ACM, vol. 64, n^o 1,‎ 2017, 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,‎ 2017, 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,‎ 2021, 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,‎ 2021, 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, n^o 3,‎ 2020, p. 597–647 (DOI 10.1002/rsa.20890, arXiv 1804.02293)

Notes et références

Liens externes

• Page personnelle de David Richerby

• Ressources relatives à la recherche :
  • Digital Bibliography & Library Project
  • Google Scholar
  • Mathematics Genealogy Project

• Portail des mathématiques
• Portail de l'informatique théorique