Accueil🇫🇷Chercher

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.

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

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

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.