David Richerby
# 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. 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 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)
