Andrei A. Bulatov

Biographie

Naissance	11 janvier 1975 (49 ans)
Formation	Université d'État de l'Oural Gorki
Activité	Mathématicien

Autres informations

A travaillé pour	Université Simon Fraser
Dir. de thèse	Evgeny Vital'evich Sukhanov (d)
Distinction	Prix Gödel (2021)

modifier - modifier le code - modifier Wikidata

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, n^o 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, n^o 5,‎ 28 octobre 2013, 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,‎ 2008, 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, n^o 2,‎ janvier 2014, p. 573–616 (lire en ligne)
• Andrei A. Bulatov, « Complexity of conservative constraint satisfaction problems », ACM Transactions on Computational Logic, vol. 12, n^o 4,‎ 22 juillet 2011, 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,‎ 1^er mai 2020, 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),‎ octobre 2017, 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 » (n^o 7913), 2013, xii + 445 (ISBN 978-3-642-38535-3, zbMATH 1264.68003).