Andrei Arnoldowitsch Bulatow (russisch Андрей Арнольдович Булатов; * 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.
Schriften (Auswahl)
Außer die im Haupttext zitierten Arbeiten.
- mit P. Jeavons, A. A. Krokhin: Constraint satisfaction problems and finite algebras, International Colloquium on Automata, Languages, and Programming (ICALP), 2000, S. 272–282
- Tractable conservative constraint satisfaction problems, Proc. 18th Annual IEEE Symposium of Logic in Computer Science, 2003
- mit P. Jeavons, A. Krokhin: Classifying the complexity of constraints using finite algebras, SIAM J. on Computing, Band 34, 2005, S. 720–742
- mit Martin Grohe: The complexity of partition functions, Theoretical Computer Science, Band 348, 2005, S. 148–186.
- A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM, Band 53, 2006, S. 66–120
- mit Víctor Dalmau: Towards a dichotomy theorem for the counting constraint satisfaction problem, Information and Computation, Band 205, 2007, S. 651–678.
- mit D. Marx: Constraint satisfaction problems and global cardinality constraints, Commun. ACM, Band 53, Heft 9, 2010, S. 99–106
- Complexity of conservative constraint satisfaction problems, ACM Transactions on Computational Logic (TOCL), Band 12, 2011, S. 1–66
- A dichotomy theorem for nonuniform CSPs, IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017
- Herausgeber mit Arseny Shur: Computer Science – Theory and Applications, Proc. 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013, Springer 2013
- Constraint satisfaction problems: complexity and algorithms, SILOG News, Band 5, Nr. 4, 2018, S. 4–24