| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activité |
| A travaillé pour | |
|---|---|
| Dir. de thèse |
Evgeny Vital'evich Sukhanov (d) |
| Distinction |
Prix Gödel () |
Andreï Arnoldovitch Boulatov (en russe : Андрей Арнольдович Булатов, orthographié à l'anglaise : Andrei A. Bulatov) est un informaticien et mathématicien russo-canadien ; né le 11 janvier 1975 à Alapaïevsk ; il est professeur d'informatique à l'université Simon Fraser.
Carrière professionnelle
Bulatov a obtenu sa maîtrise à l'Université d'État de l'Oural à Iekaterinbourg en 1991 et son doctorat en 1995, supervisé par Evgeny Sukhanov (titre de sa thèse :Algebraic Properties of the Lattice of Clones)[1]. Il est professeur associé à l'Université de l'Oural puis chercheur (research officer) à l'université d'Oxford.
À partir de 2004 il est à l'Université Simon Fraser, où il est devenu professeur. Il a obtenu son doctorat russe (habilitation) en 2008 à l'Université de l'Oural. Au printemps 2016, il est Visiting Scientist and Program Organizer au Simons Institute sur le thème « Counting Complexity and Phase Transitions »[2].
Recherche
Bulatov travaille sur le problème SAT et des problèmes de satisfaction de contraintes (CSP), en théorie de complexité, en combinatoire, sur le clonage et l'algèbre universelle (notamment le décompte d'homomorphismes ).
Prix et distinctions
En 2021, il a reçu le prix Gödel pour son article « The Complexity of the Counting Constraint Satisfaction Problem »[3],[4]. Comme pour les autres récipiendaires du prix Gödel 2021, ce travail est reconnu comme représentant l'aboutissement de la classification de la complexité de l'énumération des problèmes de satisfaction de contraintes (CSP). Ensemble, les auteurs prouvent un théorème de dichotomie pour la complexité du problème de compter les problèmes de type CSP exprimables sous forme de fonction de partition[4].
En 2014, Bulatov est conférencier invité au Congrès international des mathématiciens de Séoul (titre de sa communication : « Counting Constraint Satisfaction Problems »).
En 2021, il est conférencier invité à l'International Colloquium on Automata, Languages and Programming (ICALP).
En 2022, il a reçu le prix Cathleen Synge Morawetz de la Société mathématique du Canada[5]
En 2017, il a reçu un Best Paper Award au FOCS pour l'article « A dichotomy theorem for nonuniform CSPs ».
Publications (sélection)
- Andrei A. Bulatov, « Complexity column », ACM SIGLOG News, vol. 9, no 3, 25 août 2022, 29 pages (DOI 10.1145/3559736.3559739)
- Andrei A. Bulatov, « The complexity of the counting constraint satisfaction problem », Journal of the ACM, vol. 60, no 5, , p. 34:1–34:41 (DOI 10.1145/2528400, lire en ligne)
- Andrei A. Bulatov, « The Complexity of the Counting Constraint Satisfaction Problem », Automata, Languages and Programming, Springer, , p. 646–661 (ISBN 978-3-540-70575-8, DOI 10.1007/978-3-540-70575-8_53)
- Andrei A. Bulatov et Dániel Marx, « Constraint satisfaction parameterized by solution size », SIAM Journal on Computing, vol. 43, no 2, , p. 573–616 (lire en ligne)
- Andrei A. Bulatov, « Complexity of conservative constraint satisfaction problems », ACM Transactions on Computational Logic, vol. 12, no 4, , p. 24:1–24:66 (DOI 10.1145/1970398.1970400, zbMATH 1351.68113, lire en ligne)
- Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg et Colin McQuillan, « Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin », Journal of Computer and System Sciences, vol. 109, , p. 95–125 (DOI 10.1016/j.jcss.2019.12.003, lire en ligne)
- Andrei A. Bulatov, « A dichotomy theorem for nonuniform CSPs », 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), , p. 319–330 (DOI 10.1109/FOCS.2017.37, arXiv 2007.09099, lire en ligne) — « Best paper award ». La version dans Arxiv est « améliorée ».
- Andrei A. Bulatov et Arseny M. Shur (éditeurs), Computer science – theory and applications : 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013, Springer, coll. « Lecture Notes in Computer Science » (no 7913), , xii + 445 (ISBN 978-3-642-38535-3, zbMATH 1264.68003).
Liens externes
- Ressources relatives à la recherche :
- Page personnelle sur l'université Simon Fraser
- Page sur mathnet.ru
- Publications disponibles sur le site de l’auteur.
Références
- (en) « Andreĭ A. Bulatov », sur le site du Mathematics Genealogy Project.
- Andrei Bulatov au Simons Institute.
- Bulatov 2013.
- Gödel Prize 2021.
- Cathleen Synge Morawetz Prize 2022 « Prix Cathleen Synge Morawetz 2022 décerné à Andrei A. Bulatov », Société mathématique du Canada
