Andrei A. Bulatov

According to our database, Andrei A. Bulatov authored at least 87 papers between 2000 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Modular Counting over 3-Element and Conservative Domains.

Andrei A. Bulatov, Amirhossein Kazeminia

CoRR, October, 2025

Modular Counting CSP: Reductions and Algorithms.

Amirhossein Kazeminia, Andrei A. Bulatov

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Satisfiability of Commutative vs. Non-Commutative CSPs.

Andrei A. Bulatov, Stanislav Zivný

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Complexity Column.

Andrei Bulatov

ACM SIGLOG News, April, 2024

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

TheoretiCS, 2024

2022

On the complexity of CSP-based ideal membership problems.

Andrei A. Bulatov, Akbar Rafiey

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Complexity classification of counting graph homomorphisms modulo a prime number.

Andrei A. Bulatov, Amirhossein Kazeminia

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The Ideal Membership Problem and Abelian Groups.

Andrei A. Bulatov, Akbar Rafiey

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution.

Oleksii Omelchenko, Andrei A. Bulatov

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Symmetries and Complexity (Invited Talk).

Andrei A. Bulatov

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Satisfiability and Algorithms for Non-uniform Random k-SAT.

Oleksii Omelchenko, Andrei Bulatov

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

Algebra of Modular Systems: Containment and Equivalence.

Andrei Bulatov, Eugenia Ternovska

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.

Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivný

J. Comput. Syst. Sci., 2020

A dichotomy theorem for nonuniform CSPs simplified.

Andrei A. Bulatov

CoRR, 2020

Local structure of idempotent algebras II.

Andrei A. Bulatov

CoRR, 2020

Local structure of idempotent algebras I.

Andrei A. Bulatov

CoRR, 2020

Counting Homomorphisms in Plain Exponential Time.

Andrei A. Bulatov, Amineh Dadsetan

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

The Subpower Membership Problem for Finite Algebras with Cube Terms.

Andrei Bulatov, Peter Mayr, Ágnes Szendrei

Log. Methods Comput. Sci., 2019

Long range actions, connectedness, and dismantlability in relational structures.

Raimundo Briceño, Andrei Bulatov, Víctor Dalmau, Benoît Larose

CoRR, 2019

Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model.

Oleksii Omelchenko, Andrei A. Bulatov

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

Counting Homomorphisms Modulo a Prime Number.

Amirhossein Kazeminia, Andrei A. Bulatov

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Approximate Counting CSP Seen from the Other Side.

Andrei A. Bulatov, Stanislav Zivný

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

A short story of the CSP dichotomy conjecture.

Andrei A. Bulatov

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

Dismantlability, Connectedness, and Mixing in Relational Structures.

Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Constraint Satisfaction Problems: Complexity and Algorithms.

Andrei A. Bulatov

Proceedings of the Language and Automata Theory and Applications, 2018

2017

Functional clones and expressibility of partition functions.

Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný

Theor. Comput. Sci., 2017

Preface.

Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin

Theory Comput. Syst., 2017

Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?

Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev

Electron. J. Comb., 2017

Constraint satisfaction problems over semilattice block Mal'tsev algebras.

Andrei A. Bulatov

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

A Dichotomy Theorem for Nonuniform CSPs.

Andrei A. Bulatov

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Preface.

Andrei Bulatov, Stephan Kreutzer

Theory Comput. Syst., 2016

Conservative constraint satisfaction re-revisited.

Andrei A. Bulatov

J. Comput. Syst. Sci., 2016

The subpower membership problem for semigroups.

Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl

Int. J. Algebra Comput., 2016

The subpower membership problem for semigroups.

Andrei Bulatov, Peter Mayr, Markus Steindl

CoRR, 2016

Graphs of finite algebras, edges, and connectivity.

Andrei A. Bulatov

CoRR, 2016

Graphs of relational structures: restricted types.

Andrei A. Bulatov

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

2015

Galois Correspondence for Counting Quantifiers.

Andrei A. Bulatov, Amir Hedayaty

J. Multiple Valued Log. Soft Comput., 2015

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).

Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx

Dagstuhl Reports, 2015

Phase Transition for Local Search on Planted SAT.

Andrei A. Bulatov, Evgeny S. Skvortsov

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

Approximating Highly Satisfiable Random 2-SAT.

Andrei A. Bulatov, Cong Wang

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Inferring Attitude in Online Social Networks Based on Quadratic Correlation.

Cong Wang, Andrei A. Bulatov

Proceedings of the Advances in Knowledge Discovery and Data Mining, 2014

2013

The expressibility of functions on the boolean domain, with applications to counting CSPs.

Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan

J. ACM, 2013

Boolean Max-Co-Clones.

Andrei A. Bulatov

Proceedings of the 43rd IEEE International Symposium on Multiple-Valued Logic, 2013

Descriptive complexity of approximate counting CSPs.

Andrei A. Bulatov, Víctor Dalmau, Marc Thurley

Proceedings of the Computer Science Logic 2013, 2013

2012

Counting Problems and Clones of Functions.

Andrei A. Bulatov, Amir Hedayaty

J. Multiple Valued Log. Soft Comput., 2012

The complexity of weighted and unweighted #CSP.

Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby

J. Comput. Syst. Sci., 2012

Log-supermodular functions, functional clones and counting CSPs.

Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Greedy Algorithms, Ordering of Variables, and d-degenerate Instances.

Cong Wang, Andrei A. Bulatov

Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic, 2012

Counting Predicates, Subset Surjective Functions, and Counting CSPs.

Andrei A. Bulatov, Amir Hedayaty

Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic, 2012

2011

Complexity of conservative constraint satisfaction problems.

Andrei A. Bulatov

ACM Trans. Comput. Log., 2011

Constraint Satisfaction Parameterized by Solution Size.

Andrei A. Bulatov, Dániel Marx

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

On the CSP Dichotomy Conjecture.

Andrei A. Bulatov

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Constraint satisfaction problems and global cardinality constraints.

Andrei A. Bulatov, Dániel Marx

Commun. ACM, 2010

2009

The complexity of weighted Boolean #CSP with mixed signs.

Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby

Theor. Comput. Sci., 2009

The complexity of constraint satisfaction games and QCSP.

Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin

Inf. Comput., 2009

Enumerating Homomorphisms.

Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

The Complexity of Global Cardinality Constraints.

Andrei A. Bulatov, Dániel Marx

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Counting Problems and Clones of Functions.

Andrei A. Bulatov

Proceedings of the ISMVL 2009, 2009

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.

Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

2008

The Complexity of the Counting Constraint Satisfaction Problem.

Andrei A. Bulatov

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Recent Results on the Algebraic Approach to the CSP.

Andrei A. Bulatov, Matthew Valeriote

Proceedings of the Complexity of Constraints, 2008

Dualities for Constraint Satisfaction Problems.

Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose

Proceedings of the Complexity of Constraints, 2008

2007

Learning intersection-closed classes with signatures.

Andrei A. Bulatov, Hubie Chen, Víctor Dalmau

Theor. Comput. Sci., 2007

Affine Systems of Equations and Counting Infinitary Logic.

Albert Atserias, Andrei A. Bulatov, Anuj Dawar

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

On the Power of <i>k</i> -Consistency.

Albert Atserias, Andrei A. Bulatov, Víctor Dalmau

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

A Simple Algorithm for Mal'tsev Constraints.

Andrei A. Bulatov, Víctor Dalmau

SIAM J. Comput., 2006

A dichotomy theorem for constraint satisfaction problems on a 3-element set.

Andrei A. Bulatov

J. ACM, 2006

Efficiency of Local Search.

Andrei A. Bulatov, Evgeny S. Skvortsov

Proceedings of the Theory and Applications of Satisfiability Testing, 2006

2005

H-Coloring dichotomy revisited.

Andrei A. Bulatov

Theor. Comput. Sci., 2005

Classifying the Complexity of Constraints Using Finite Algebras.

Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin

SIAM J. Comput., 2005

2004

A Graph of a Relational Structure and Constraint Satisfaction Problems.

Andrei A. Bulatov

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

The Complexity of Partition Functions.

Andrei A. Bulatov, Martin Grohe

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Learnability of Relatively Quantified Generalized Formulas.

Andrei A. Bulatov, Hubie Chen, Víctor Dalmau

Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003

Counting Mal'tsev clones on small sets.

Andrei A. Bulatov, Pawel M. Idziak

Discret. Math., 2003

Tractable conservative Constraint Satisfaction Problems.

Andrei A. Bulatov

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons

Proceedings of the 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2003), 2003

Amalgams of Constraint Satisfaction Problems.

Andrei A. Bulatov, Evgeny S. Skvortsov

Proceedings of the IJCAI-03, 2003

Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem.

Andrei A. Bulatov, Víctor Dalmau

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Quantified Constraints: Algorithms and Complexity.

Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

An Algebraic Approach to Multi-sorted Constraints.

Andrei A. Bulatov, Peter Jeavons

Proceedings of the Principles and Practice of Constraint Programming, 2003

2002

Mal'tsev constraints are tractable

Andrei A. Bulatov

Electron. Colloquium Comput. Complex., 2002

Tractable Constraint Satisfaction Problems on a 3-element set

Andrei A. Bulatov

Electron. Colloquium Comput. Complex., 2002

A Dichotomy Theorem for Constraints on a Three-Element Set.

Andrei A. Bulatov

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

The complexity of maximal constraint languages.

Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Constraint Satisfaction Problems and Finite Algebras.

Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000