Андрей Арнольдович Булатов (род. 11 января 1976, Алапаевск, СССР) — доктор физико-математических наук, профессор, доцент, лауреат премии Гёделя (2021).
Биография Родился в Алапаевске Свердловской области.
Окончил математико-механический факультет Уральского государственного университета по специальности «математика». По 2002 год работал в УрГУ, с 2002 по 2005 год обучался в докторантуре университета под руководством профессора Л. Н. Шеврина. В настоящее время работает в Университете Саймона Фрейзера в Канаде.
Автор множества научных и учебно-методических работ. Выполнил циклы исследований по решеткам клонов и по приложениям универсальной алгебры к теории сложности вычислений. В 2002 году был удостоен приза за лучшую работу на 43-м Международном симпозиуме по основаниям компьютерных наук в Ванкувере в США. Лауреат премии УФУ за высокие достижения в учебно-методической деятельности в 2006 году.
Основные труды Bulatov, Andrei A. Constraint satisfaction problems: complexity and algorithms. (English) Zbl 06894736 Klein, Shmuel Tomi (ed.) et al., Language and automata theory and applications. 12th international conference, LATA 2018, Ramat Gan, Israel, April 9—11, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-77312-4/pbk; 978-3-319-77313-1/ebook). Lecture Notes in Computer Science 10792, 1-25 (2018). MSC: 68Q45 Bulatov, Andrei A. (ed.); Hirsch, Edward A. (ed.); Pin, Jean-Éric (ed.) Preface. (English) Zbl 1372.00093 Theory Comput. Syst. 61, No. 2, 261—262 (2017). MSC: 00B25 68-06 Bulatov, Andrei A.; Karpova, Olga; Shur, Arseny M.; Startsev, Konstantin Lower bounds on words separation: are there short identities in transformation semigroups? (English) Zbl 1372.68156 Electron. J. Comb. 24, No. 3, Research Paper P3.35, 12 p. (2017). MSC: 68Q45 20B30 20M20 68Q70 68R15 Bulatov, Andrei; Goldberg, Leslie Ann; Jerrum, Mark; Richerby, David; Živný, Stanislav Functional clones and expressibility of partition functions. (English) Zbl 06730360 Theor. Comput. Sci. 687, 11-39 (2017). MSC: 08A40 Bulatov, Andrei A. Graphs of relational structures, restricted types. (English) Zbl 06863534 Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5—8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 642—651 (2016). MSC: 68Q25 05C25 Bulatov, A. (ed.); Kreutzer, S. (ed.) Preface. (English) Zbl 1354.00085 Theory Comput. Syst. 59, No. 2, 159—160 (2016). MSC: 00B25 68-06 Bulatov, Andrei; Kozik, Marcin; Mayr, Peter; Steindl, Markus The subpower membership problem for semigroups. (English) Zbl 06663545 Int. J. Algebra Comput. 26, No. 7, 1435—1451 (2016). MSC: 20M99 68Q25 Bulatov, Andrei A. Conservative constraint satisfaction re-revisited. (English) Zbl 1346.68108 J. Comput. Syst. Sci. 82, No. 2, 347—356 (2016). MSC: 68Q25 Bulatov, Andrei A.; Hedayaty, Amir Galois correspondence for counting quantifiers. (English) Zbl 06930501 J. Mult.-Val. Log. Soft Comput. 24, No. 5-6, 405—424 (2015). MSC: 08A70 08A40 06A15 68Q25 Bulatov, Andrei A.; Skvortsov, Evgeny S. Phase transition for local search on planted SAT. (English) Zbl 06482807 Italiano, F. (ed.) et al., Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24—28, 2015. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-48053-3/pbk; 978-3-662-48054-0/ebook). Lecture Notes in Computer Science 9235, 175—186 (2015). MSC: 68Qxx Bulatov, Andrei A. Boolean max-co-clones. (English) Zbl 1348.08004 Algebra Univers. 74, No. 1-2, 139—162 (2015). Reviewer: Lavinia Ciungu (Iowa City) MSC: 08A70 08A40 06B99 Bulatov, Andrei A. Counting constraint satisfaction problems. (English) Zbl 1373.68255 Jang, Sun Young (ed.) et al., Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13—21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa (ISBN 978-89-6105-807-0/hbk; 978-89-6105-803-2/set). 561—584 (2014). MSC: 68Q25 68Q17 Bulatov, Andrei A.; Wang, Cong Approximating highly satisfiable random 2-SAT. (English) Zbl 06348076 Sinz, Carsten (ed.) et al., Theory and applications of satisfiability testing — SAT 2014. 17th international conference, held as part of the Vienna summer of logic, VSL 2014, Vienna, Austria, July 14—17, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-09283-6/pbk). Lecture Notes in Computer Science 8561, 384—398 (2014). MSC: 68Q25 68T20 Bulatov, Andrei A.; Marx, Dániel Constraint satisfaction parameterized by solution size. (English) Zbl 1360.68499 SIAM J. Comput. 43, No. 2, 573—616 (2014). MSC: 68Q25 68Q17 Bulatov, Andrei; Dalmau, Victor; Thurley, Marc Descriptive complexity of approximate counting CSPs. (English) Zbl 1356.68090 Ronchi della Rocca, Simona (ed.), Computer science logic 2013. Selected papers of the 27th CSL workshop and 22nd annual conference of the European Association for Computer Science Logic (EACSL), Torino, Italy, September 2—5, 2013. Wadern: Schloss Dagstuhl — Leibniz Zentrum für Informatik (ISBN 978-3-939897-60-6). LIPICS — Leibniz International Proceedings in Informatics 23, 149—164 (2013). MSC: 68Q19 Bulatov, Andrei A. The complexity of the counting constraint satisfaction problem. (English) Zbl 1281.68130 J. ACM 60, No. 5, Article No. 34, 41 p. (2013). MSC: 68Q25 08A40 08A70 68Q15 68T20 Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Mcquillan, Colin The expressibility of functions on the Boolean domain, with applications to counting CSPs. (English) Zbl 1281.68131 J. ACM 60, No. 5, Article No. 32, 36 p. (2013). MSC: 68Q25 68W25 90C60 Bulatov, Andrei A. (ed.); Shur, Arseny M. (ed.) Computer science — theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25—29, 2013. Proceedings. (English) Zbl 1264.68003 Lecture Notes in Computer Science 7913. Berlin: Springer (ISBN 978-3-642-38535-3/pbk). xii, 445 p. (2013). MSC: 68-06 68Qxx 00B25 Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark Log-supermodular functions, functional clones and counting CSPs. (English) Zbl 1245.68100 Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th — March 3rd, 2012. Wadern: Schloss Dagstuhl — Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPICS — Leibniz International Proceedings in Informatics 14, 302—313, electronic only (2012). MSC: 68Q25 68Q15 Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David The complexity of weighted and unweighted #CSP. (English) Zbl 1282.68110 J. Comput. Syst. Sci. 78, No. 2, 681—688 (2012). MSC: 68Q15 Bulatov, Andrei A.; Dalmau, Víctor; Grohe, Martin; Marx, Dániel Enumerating homomorphisms. (English) Zbl 1253.68165 J. Comput. Syst. Sci. 78, No. 2, 638—650 (2012). MSC: 68Q25 05C30 68R05 Bulatov, Andrei A.; Hedayaty, Amir Counting problems and clones of functions. (English) Zbl 1236.68194 J. Mult.-Val. Log. Soft Comput. 18, No. 2, 117—138 (2012). MSC: 68R05 03B50 08A40 68Q25 Bulatov, Andrei A. Complexity of conservative constraint satisfaction problems. (English) Zbl 1351.68113 ACM Trans. Comput. Log. 12, No. 4, Article No. 24, 66 p. (2011). MSC: 68Q25 05C15 68T20 Bulatov, Andrei A.; Marx, Dániel Constraint satisfaction parameterized by solution size. (English) Zbl 1333.68136 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4—8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 424—436 (2011). MSC: 68Q25 68Q17 Bulatov, Andrei A. On the CSP dichotomy conjecture. (English) Zbl 1332.68065 Kulikov, Alexander (ed.) et al., Computer science — theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14—18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 331—344 (2011). MSC: 68Q25 68T20 Bulatov, Andrei A.; Marx, Daniel The complexity of global cardinality constraints. (English) Zbl 1202.68208 Log. Methods Comput. Sci. 6, No. 4, Paper No. 4, 27 p. (2010). MSC: 68Q25 Bulatov, Andrei A.; Dalmau, Víctor; Grohe, Martin; Marx, Dániel Enumerating homomorphisms. (English) Zbl 1236.68105 Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26—28, 2009. Wadern: Schloss Dagstuhl — Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPICS — Leibniz International Proceedings in Informatics 3, 231—242, electronic only (2009). MSC: 68Q25 05C30 68R05 Börner, F.; Bulatov, A.; Chen, H.; Jeavons, P.; Krokhin, A. The complexity of constraint satisfaction games and QCSP. (English) Zbl 1188.68269 Inf. Comput. 207, No. 9, 923—944 (2009). MSC: 68T20 68Q25 91A05 Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David The complexity of weighted Boolean #CSP with mixed signs. (English) Zbl 1171.68013 Theor. Comput. Sci. 410, No. 38-40, 3949-3961 (2009). MSC: 68Q25 68T20 Atserias, Albert; Bulatov, Andrei; Dawar, Anuj Affine systems of equations and counting infinitary logic. (English) Zbl 1168.68040 Theor. Comput. Sci. 410, No. 18, 1666—1683 (2009). MSC: 68T20 03C13 03C75 08A70 68Q25 Bulatov, Andrei A.; Krokhin, Andrei; Larose, Benoit Dualities for constraint satisfaction problems. (English) Zbl 1171.68494 Creignou, Nadia (ed.) et al., Complexity of constraints. An overview of current research themes. Berlin: Springer (ISBN 978-3-540-92799-0/pbk). Lecture Notes in Computer Science 5250, 93-124 (2008). MSC: 68Q25 03B70 08A70 Bulatov, Andrei A.; Valeriote, Matthew A. Recent results on the algebraic approach to the CSP. (English) Zbl 1171.08300 Creignou, Nadia (ed.) et al., Complexity of constraints. An overview of current research themes. Berlin: Springer (ISBN 978-3-540-92799-0/pbk). Lecture Notes in Computer Science 5250, 68-92 (2008). MSC: 08A70 03B70 Bulatov, Andrei A. The complexity of the counting constraint satisfaction problem. (English) Zbl 1153.68386 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7—11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 646—661 (2008). MSC: 68Q25 Atserias, Albert; Bulatov, Andrei; Dawar, Anuj Affine systems of equations and counting infinitary logic. (English) Zbl 1171.68721 Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocł aw, Poland, July 9—13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 558—570 (2007). MSC: 68T20 03C13 03C75 08A70 68Q25 Atserias, Albert; Bulatov, Andrei; Dalmau, Victor On the power of k-consistency. (English) Zbl 1171.68720 Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocł aw, Poland, July 9—13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 279—290 (2007). MSC: 68T20 Bulatov, Andrei; Chen, Hubie; Dalmau, Víctor Learning intersection-closed classes with signatures. (English) Zbl 1127.68044 Theor. Comput. Sci. 382, No. 3, 209—220 (2007). MSC: 68Q32 68W05 Bulatov, Andrei A.; Dalmau, Víctor Towards a dichotomy theorem for the counting constraint satisfaction problem. (English) Zbl 1115.68141 Inf. Comput. 205, No. 5, 651—678 (2007). MSC: 68T20 68Q25 Bulatov, Andrei A. A dichotomy theorem for constraint satisfaction problems on a 3-element set. (English) Zbl 1316.68057 J. ACM 53, No. 1, 66-120 (2006). MSC: 68Q25 68Q17 68T20