Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAndrei A. Bulatov
Andrei Bulatov
Person information
- affiliation: Simon Fraser University, Burnaby, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2022
[j35]Andrei Bulatov:
Complexity column. ACM SIGLOG News 9(3): 29 (2022)- [c49]Oleksii Omelchenko, Andrei A. Bulatov:
Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution. AAAI 2022: 3804-3812 - [c48]Andrei A. Bulatov, Akbar Rafiey:
The Ideal Membership Problem and Abelian Groups. STACS 2022: 18:1-18:16 - [c47]Andrei A. Bulatov, Akbar Rafiey:
On the complexity of CSP-based ideal membership problems. STOC 2022: 436-449 - [c46]Andrei A. Bulatov, Amirhossein Kazeminia:
Complexity classification of counting graph homomorphisms modulo a prime number. STOC 2022: 1024-1037 - [i36]Andrei A. Bulatov, Akbar Rafiey:
The Ideal Membership Problem and Abelian Groups. CoRR abs/2201.05218 (2022) - 2021
- [j34]Raimundo Briceño, Andrei Bulatov, Víctor Dalmau, Benoît Larose:
Dismantlability, connectedness, and mixing in relational structures. J. Comb. Theory, Ser. B 147: 37-70 (2021) - [j33]Oleksii Omelchenko, Andrei A. Bulatov:
Satisfiability threshold for power law random 2-SAT in configuration model. Theor. Comput. Sci. 888: 70-94 (2021) - [c45]Oleksii Omelchenko, Andrei Bulatov:
Satisfiability and Algorithms for Non-uniform Random k-SAT. AAAI 2021: 3886-3894 - [c44]Andrei Bulatov, Eugenia Ternovska:
Algebra of Modular Systems: Containment and Equivalence. AAAI 2021: 6235-6243 - [c43]Andrei A. Bulatov:
Symmetries and Complexity (Invited Talk). ICALP 2021: 2:1-2:17 - [c42]Libor Barto
, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk:
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP. LICS 2021: 1-13 - [i35]Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk:
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP. CoRR abs/2104.11808 (2021) - [i34]Andrei A. Bulatov, Amirhossein Kazeminia:
Complexity classification of counting graph homomorphisms modulo a prime number. CoRR abs/2106.04086 (2021) - 2020
- [j32]Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivný:
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. J. Comput. Syst. Sci. 109: 95-125 (2020) - [j31]Andrei A. Bulatov, Stanislav Zivný:
Approximate Counting CSP Seen from the Other Side. ACM Trans. Comput. Theory 12(2): 11:1-11:19 (2020) - [c41]Andrei A. Bulatov, Amineh Dadsetan:
Counting Homomorphisms in Plain Exponential Time. ICALP 2020: 21:1-21:18 - [i33]Andrei A. Bulatov:
Local structure of idempotent algebras I. CoRR abs/2006.09599 (2020) - [i32]Andrei A. Bulatov:
Local structure of idempotent algebras II. CoRR abs/2006.10239 (2020) - [i31]Andrei A. Bulatov:
Graphs of relational structures: restricted types. CoRR abs/2006.11713 (2020) - [i30]Andrei A. Bulatov:
A dichotomy theorem for nonuniform CSPs simplified. CoRR abs/2007.09099 (2020) - [i29]Andrei A. Bulatov, Akbar Rafiey:
On the Complexity of CSP-based Ideal Membership Problems. CoRR abs/2011.03700 (2020)
2010 – 2019
- 2019
- [j30]Andrei A. Bulatov:
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. Inf. Comput. 268 (2019) - [j29]Andrei Bulatov, Peter Mayr, Ágnes Szendrei:
The Subpower Membership Problem for Finite Algebras with Cube Terms. Log. Methods Comput. Sci. 15(1) (2019) - [c40]Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose:
Dismantlability, Connectedness, and Mixing in Relational Structures. ICALP 2019: 29:1-29:15 - [c39]Andrei A. Bulatov:
A short story of the CSP dichotomy conjecture. LICS 2019: 1 - [c38]Amirhossein Kazeminia, Andrei A. Bulatov:
Counting Homomorphisms Modulo a Prime Number. MFCS 2019: 59:1-59:13 - [c37]Andrei A. Bulatov, Stanislav Zivný:
Approximate Counting CSP Seen from the Other Side. MFCS 2019: 60:1-60:14 - [c36]Oleksii Omelchenko, Andrei A. Bulatov:
Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. SAT 2019: 53-70 - [i28]Raimundo Briceño, Andrei Bulatov, Víctor Dalmau, Benoît Larose:
Long range actions, connectedness, and dismantlability in relational structures. CoRR abs/1901.04398 (2019) - [i27]Oleksii Omelchenko, Andrei A. Bulatov:
Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. CoRR abs/1905.04827 (2019) - [i26]Amirhossein Kazeminia, Andrei A. Bulatov:
Counting Homomorphisms Modulo a Prime Number. CoRR abs/1905.10682 (2019) - [i25]Andrei A. Bulatov, Stanislav Zivný:
Approximate counting CSP seen from the other side. CoRR abs/1907.07922 (2019) - 2018
- [j28]Andrei A. Bulatov:
Constraint satisfaction problems: complexity and algorithms. ACM SIGLOG News 5(4): 4-24 (2018) - [c35]Andrei A. Bulatov:
Constraint Satisfaction Problems: Complexity and Algorithms. LATA 2018: 1-25 - [i24]Andrei Bulatov, Peter Mayr, Ágnes Szendrei:
The Subpower Membership Problem for Finite Algebras with Cube Terms. CoRR abs/1803.08019 (2018) - [i23]Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivný:
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. CoRR abs/1804.04993 (2018) - [i22]Amineh Dadsetan, Andrei A. Bulatov:
Counting homomorphisms in plain exponential time. CoRR abs/1810.03087 (2018) - 2017
- [j27]Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev:
Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? Electron. J. Comb. 24(3): 3 (2017) - [j26]Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin:
Preface. Theory Comput. Syst. 61(2): 261-262 (2017) - [j25]Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný:
Functional clones and expressibility of partition functions. Theor. Comput. Sci. 687: 11-39 (2017) - [c34]Andrei A. Bulatov:
A Dichotomy Theorem for Nonuniform CSPs. FOCS 2017: 319-330 - [c33]Andrei A. Bulatov:
Constraint satisfaction problems over semilattice block Mal'tsev algebras. LICS 2017: 1-11 - [i21]Andrei A. Bulatov:
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. CoRR abs/1701.02623 (2017) - [i20]Andrei A. Bulatov:
A dichotomy theorem for nonuniform CSPs. CoRR abs/1703.03021 (2017) - 2016
- [j24]Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl:
The subpower membership problem for semigroups. Int. J. Algebra Comput. 26(7): 1435-1451 (2016) - [j23]Andrei A. Bulatov:
Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci. 82(2): 347-356 (2016) - [j22]Andrei Bulatov, Stephan Kreutzer:
Preface. Theory Comput. Syst. 59(2): 159-160 (2016) - [c32]Andrei A. Bulatov:
Graphs of relational structures: restricted types. LICS 2016: 642-651 - [i19]Andrei A. Bulatov:
Graphs of finite algebras, edges, and connectivity. CoRR abs/1601.07403 (2016) - [i18]Andrei Bulatov, Peter Mayr, Markus Steindl:
The subpower membership problem for semigroups. CoRR abs/1603.09333 (2016) - [i17]Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev:
Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? CoRR abs/1609.03199 (2016) - [i16]Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný:
Functional Clones and Expressibility of Partition Functions. CoRR abs/1609.07377 (2016) - 2015
- [j21]Andrei A. Bulatov, Amir Hedayaty:
Galois Correspondence for Counting Quantifiers. J. Multiple Valued Log. Soft Comput. 24(5-6): 405-424 (2015) - [c31]Andrei A. Bulatov, Evgeny S. Skvortsov:
Phase Transition for Local Search on Planted SAT. MFCS (2) 2015: 175-186 - [i15]Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports 5(7): 22-41 (2015) - 2014
- [j20]Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. SIAM J. Comput. 43(2): 573-616 (2014) - [c30]Cong Wang, Andrei A. Bulatov:
Inferring Attitude in Online Social Networks Based on Quadratic Correlation. PAKDD (1) 2014: 139-150 - [c29]Andrei A. Bulatov, Cong Wang:
Approximating Highly Satisfiable Random 2-SAT. SAT 2014: 384-398 - [i14]Andrei A. Bulatov:
Conservative constraint satisfaction re-revisited. CoRR abs/1408.3690 (2014) - 2013
- [j19]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan:
The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM 60(5): 32:1-32:36 (2013) - [j18]Andrei A. Bulatov:
The complexity of the counting constraint satisfaction problem. J. ACM 60(5): 34:1-34:41 (2013) - [c28]Andrei A. Bulatov, Víctor Dalmau, Marc Thurley:
Descriptive complexity of approximate counting CSPs. CSL 2013: 149-164 - [c27]Andrei A. Bulatov:
Boolean Max-Co-Clones. ISMVL 2013: 192-197 - [e2]Andrei A. Bulatov, Arseny M. Shur:
Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings. Lecture Notes in Computer Science 7913, Springer 2013, ISBN 978-3-642-38535-3 [contents] - 2012
- [j17]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating homomorphisms. J. Comput. Syst. Sci. 78(2): 638-650 (2012) - [j16]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby:
The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78(2): 681-688 (2012) - [j15]Andrei A. Bulatov, Amir Hedayaty:
Counting Problems and Clones of Functions. J. Multiple Valued Log. Soft Comput. 18(2): 117-138 (2012) - [c26]Cong Wang, Andrei A. Bulatov:
Greedy Algorithms, Ordering of Variables, and d-degenerate Instances. ISMVL 2012: 31-36 - [c25]Andrei A. Bulatov, Amir Hedayaty:
Counting Predicates, Subset Surjective Functions, and Counting CSPs. ISMVL 2012: 331-336 - [c24]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Log-supermodular functions, functional clones and counting CSPs. STACS 2012: 302-313 - [i13]Andrei A. Bulatov, Dániel Marx:
Constraint satisfaction parameterized by solution size. CoRR abs/1206.4854 (2012) - [i12]Andrei A. Bulatov, Amir Hedayaty:
Galois correspondence for counting quantifiers. CoRR abs/1210.3344 (2012) - [i11]Cong Wang, Andrei A. Bulatov:
Inferring Attitude in Online Social Networks Based On Quadratic Correlation. CoRR abs/1212.1633 (2012) - 2011
- [j14]Andrei A. Bulatov:
Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12(4): 24:1-24:66 (2011) - [c23]Andrei A. Bulatov:
On the CSP Dichotomy Conjecture. CSR 2011: 331-344 - [c22]Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. ICALP (1) 2011: 424-436 - [i10]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Log-supermodular functions, functional clones and counting CSPs. CoRR abs/1108.5288 (2011) - 2010
- [j13]Andrei A. Bulatov, Dániel Marx:
Constraint satisfaction problems and global cardinality constraints. Commun. ACM 53(9): 99-106 (2010) - [j12]Andrei A. Bulatov, Dániel Marx:
The complexity of global cardinality constraints. Log. Methods Comput. Sci. 6(4) (2010) - [i9]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby:
The complexity of weighted and unweighted #CSP. CoRR abs/1005.2678 (2010)
2000 – 2009
- 2009
- [j11]Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin:
The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207(9): 923-944 (2009) - [j10]Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410(18): 1666-1683 (2009) - [j9]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. 410(38-40): 3949-3961 (2009) - [c21]Andrei A. Bulatov:
Counting Problems and Clones of Functions. ISMVL 2009: 1-6 - [c20]Andrei A. Bulatov, Dániel Marx:
The Complexity of Global Cardinality Constraints. LICS 2009: 419-428 - [c19]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. STACS 2009: 231-242 - [e1]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009. Dagstuhl Seminar Proceedings 09441, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i8]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i7]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i6]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. CoRR abs/0902.1256 (2009) - 2008
- [c18]Andrei A. Bulatov, Matthew Valeriote:
Recent Results on the Algebraic Approach to the CSP. Complexity of Constraints 2008: 68-92 - [c17]Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose:
Dualities for Constraint Satisfaction Problems. Complexity of Constraints 2008: 93-124 - [c16]Andrei A. Bulatov:
The Complexity of the Counting Constraint Satisfaction Problem. ICALP (1) 2008: 646-661 - [i5]Andrei A. Bulatov, Evgeny S. Skvortsov:
Phase transition for Local Search on planted SAT. CoRR abs/0811.2546 (2008) - [i4]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
The Complexity of Weighted Boolean #CSP with Mixed Signs. CoRR abs/0812.4171 (2008) - 2007
- [j8]Andrei A. Bulatov, Víctor Dalmau:
Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput. 205(5): 651-678 (2007) - [j7]Andrei A. Bulatov, Hubie Chen, Víctor Dalmau:
Learning intersection-closed classes with signatures. Theor. Comput. Sci. 382(3): 209-220 (2007) - [c15]Albert Atserias, Andrei A. Bulatov, Víctor Dalmau:
On the Power of k -Consistency. ICALP 2007: 279-290 - [c14]Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine Systems of Equations and Counting Infinitary Logic. ICALP 2007: 558-570 - [i3]Andrei A. Bulatov:
The complexity of the counting constraint satisfaction problem. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j6]Andrei A. Bulatov:
A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1): 66-120 (2006) - [j5]Andrei A. Bulatov, Víctor Dalmau:
A Simple Algorithm for Mal'tsev Constraints. SIAM J. Comput. 36(1): 16-27 (2006) - [c13]Andrei A. Bulatov, Evgeny S. Skvortsov:
Efficiency of Local Search. SAT 2006: 297-310 - 2005
- [j4]Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin:
Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34(3): 720-742 (2005) - [j3]Andrei A. Bulatov, Martin Grohe:
The complexity of partition functions. Theor. Comput. Sci. 348(2-3): 148-186 (2005) - [j2]Andrei A. Bulatov:
H-Coloring dichotomy revisited. Theor. Comput. Sci. 349(1): 31-39 (2005) - 2004
- [c12]Andrei A. Bulatov, Hubie Chen, Víctor Dalmau:
Learnability of Relatively Quantified Generalized Formulas. ALT 2004: 365-379 - [c11]Andrei A. Bulatov, Martin Grohe:
The Complexity of Partition Functions. ICALP 2004: 294-306 - [c10]Andrei A. Bulatov:
A Graph of a Relational Structure and Constraint Satisfaction Problems. LICS 2004: 448-457 - 2003
- [j1]Andrei A. Bulatov, Pawel M. Idziak:
Counting Mal'tsev clones on small sets. Discret. Math. 268(1-3): 59-80 (2003) - [c9]Andrei A. Bulatov, Peter Jeavons:
An Algebraic Approach to Multi-sorted Constraints. CP 2003: 183-198 - [c8]Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin:
Quantified Constraints: Algorithms and Complexity. CSL 2003: 58-70 - [c7]Andrei A. Bulatov, Víctor Dalmau:
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. FOCS 2003: 562-571 - [c6]Andrei A. Bulatov, Evgeny S. Skvortsov:
Amalgams of Constraint Satisfaction Problems. IJCAI 2003: 197-202 - [c5]Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons:
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL 2003: 343-354 - [c4]Andrei A. Bulatov:
Tractable conservative Constraint Satisfaction Problems. LICS 2003: 321- - 2002
- [c3]Andrei A. Bulatov:
A Dichotomy Theorem for Constraints on a Three-Element Set. FOCS 2002: 649-658 - [i2]Andrei A. Bulatov:
Tractable Constraint Satisfaction Problems on a 3-element set. Electron. Colloquium Comput. Complex. TR02 (2002) - [i1]Andrei A. Bulatov:
Mal'tsev constraints are tractable. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [c2]Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
The complexity of maximal constraint languages. STOC 2001: 667-674 - 2000
- [c1]Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
Constraint Satisfaction Problems and Finite Algebras. ICALP 2000: 272-282