Andrei Arnoldowitsch Bulatow

Andrei Arnoldowitsch Bulatow (russisch Андрей Арнольдович Булатов, englische Transkription Andrei Arnol'dovich Bulatov; * 11. Januar 1975 in Alapajewsk) ist ein russisch-kanadischer Informatiker und Mathematiker und Hochschullehrer an der Simon Fraser University.

Bulatow erhielt 1991 seinen Master-Abschluss an der Staatlichen Universität des Urals in Jekaterinburg und wurde dort 1995 promoviert. Er blieb einige Jahre an der Universität des Urals und an der Universität Oxford und war ab 2004 an der Simon Fraser University, an der er Professor wurde. Er habilitierte sich 2008 (russischer Doktortitel) an der Universität des Urals.

Er befasst sich mit dem SAT-Problem und Constraint Satisfaction Problems (CSP), Komplexitätstheorie, Kombinatorik, Klonen und universeller Algebra (u. a. Abzählen von Homomorphismen).

2021 erhielt er den Gödel-Preis für seine Arbeit The Complexity of the Counting Constraint Satisfaction Problem (J. ACM, Band 60, 2013, S. 1–41, und: International Colloquium on Automata, Languages and Programming, ICALP, 2008, S. 646–661). Wie die anderen Empfänger des Gödel-Preises von 2021 wurden damit Arbeiten gewürdigt, die den Höhepunkt der Klassifikation von Abzählkomplexität von Constraint Satisfaction Problems (CSP) darstellen. Sie beweisen zusammen einen umfassendes Komplexitäts-Dichotomie-Theorem für das Abzählen von CSP-artigen Problemen die als Verteilungsfunktion (partition function) ausdrückbar sind (Laudatio zum Gödel-Preis).

Er war Vortragender auf dem Internationalen Mathematikerkongress in Seoul 2014 (Counting Constraint Satisfaction Problems). 2021 war er Keynote-Speaker auf dem International Colloquium on Automata, Languages and Programming (ICALP).2022 erhielt er den Cathleen Synge Morawetz Prize der Canadian Mathematical Society.