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, no 3,‎ , 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, 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
  1. (en) « David Richerby », sur le site du Mathematics Genealogy Project.
  2. « 2021 Gödel Prize citation »

Liens externes

  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.