Naissance | |
---|---|
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.
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].
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 ).
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 ».