David Richerby

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),

modifier

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

v · m
Lauréats du prix Gödel

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!