Andrei A. Bulatov

Publication Activity (10 Years)

Years Active: 2000-2024
Publications (10 Years): 39

Top Venues

CoRR

LICS

ICALP

STOC

Publications

Andrei A. Bulatov, Stanislav Zivný
Satisfiability of commutative vs. non-commutative CSPs. CoRR (2024)
Andrei A. Bulatov, Akbar Rafiey
The Ideal Membership Problem and Abelian Groups. STACS (2022)
Andrei A. Bulatov, Akbar Rafiey
On the complexity of CSP-based ideal membership problems. STOC (2022)
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)
Andrei A. Bulatov, Akbar Rafiey
The Ideal Membership Problem and Abelian Groups. CoRR (2022)
Andrei A. Bulatov, Amirhossein Kazeminia
Complexity classification of counting graph homomorphisms modulo a prime number. STOC (2022)
Andrei A. Bulatov, Amirhossein Kazeminia
Complexity classification of counting graph homomorphisms modulo a prime number. CoRR (2021)
Oleksii Omelchenko, Andrei A. Bulatov
Satisfiability threshold for power law random 2-SAT in configuration model. Theor. Comput. Sci. 888 (2021)
Andrei A. Bulatov
Symmetries and Complexity (Invited Talk). ICALP (2021)
Andrei A. Bulatov
Graphs of relational structures: restricted types. CoRR (2020)
Andrei A. Bulatov
A dichotomy theorem for nonuniform CSPs simplified. CoRR (2020)
Andrei A. Bulatov
Local structure of idempotent algebras I. CoRR (2020)
Andrei A. Bulatov
Local structure of idempotent algebras II. CoRR (2020)
Andrei A. Bulatov, Akbar Rafiey
On the Complexity of CSP-based Ideal Membership Problems. CoRR (2020)
Andrei A. Bulatov, Stanislav Zivný
Approximate Counting CSP Seen from the Other Side. ACM Trans. Comput. Theory 12 (2) (2020)
Andrei A. Bulatov, Amineh Dadsetan
Counting Homomorphisms in Plain Exponential Time. ICALP (2020)
Andrei A. Bulatov, Stanislav Zivný
Approximate Counting CSP Seen from the Other Side. MFCS (2019)
Oleksii Omelchenko, Andrei A. Bulatov
Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. CoRR (2019)
Amirhossein Kazeminia, Andrei A. Bulatov
Counting Homomorphisms Modulo a Prime Number. CoRR (2019)
Oleksii Omelchenko, Andrei A. Bulatov
Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. SAT (2019)
Andrei A. Bulatov, Stanislav Zivný
Approximate counting CSP seen from the other side. CoRR (2019)
Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose
Dismantlability, Connectedness, and Mixing in Relational Structures. ICALP (2019)
Amirhossein Kazeminia, Andrei A. Bulatov
Counting Homomorphisms Modulo a Prime Number. MFCS (2019)
Andrei A. Bulatov
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. Inf. Comput. 268 (2019)
Andrei A. Bulatov
A short story of the CSP dichotomy conjecture. LICS (2019)
Amineh Dadsetan, Andrei A. Bulatov
Counting homomorphisms in plain exponential time. CoRR (2018)
Andrei A. Bulatov
Constraint satisfaction problems: complexity and algorithms. ACM SIGLOG News 5 (4) (2018)
Andrei A. Bulatov
Constraint Satisfaction Problems: Complexity and Algorithms. LATA (2018)
Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin
Preface. Theory Comput. Syst. 61 (2) (2017)
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) (2017)
Andrei A. Bulatov
A Dichotomy Theorem for Nonuniform CSPs. FOCS (2017)
Andrei A. Bulatov
Constraint satisfaction problems over semilattice block Mal'tsev algebras. LICS (2017)
Andrei A. Bulatov
A dichotomy theorem for nonuniform CSPs. CoRR (2017)
Andrei A. Bulatov
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. CoRR (2017)
Andrei A. Bulatov
Graphs of relational structures: restricted types. LICS (2016)
Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev
Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? CoRR (2016)
Andrei A. Bulatov
Graphs of finite algebras, edges, and connectivity. CoRR (2016)
Andrei A. Bulatov
Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci. 82 (2) (2016)
Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
Functional Clones and Expressibility of Partition Functions. CoRR (2016)
Andrei A. Bulatov, Evgeny S. Skvortsov
Phase Transition for Local Search on Planted SAT. MFCS (2) (2015)
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) (2015)
Andrei A. Bulatov, Amir Hedayaty
Galois Correspondence for Counting Quantifiers. J. Multiple Valued Log. Soft Comput. 24 (5-6) (2015)
Andrei A. Bulatov, Dániel Marx
Constraint Satisfaction Parameterized by Solution Size. SIAM J. Comput. 43 (2) (2014)
Andrei A. Bulatov
Conservative constraint satisfaction re-revisited. CoRR (2014)
Andrei A. Bulatov, Cong Wang
Approximating Highly Satisfiable Random 2-SAT. SAT (2014)
Cong Wang, Andrei A. Bulatov
Inferring Attitude in Online Social Networks Based on Quadratic Correlation. PAKDD (1) (2014)
Andrei A. Bulatov
Boolean Max-Co-Clones. ISMVL (2013)
Andrei A. Bulatov
The complexity of the counting constraint satisfaction problem. J. ACM 60 (5) (2013)
Andrei A. Bulatov, Víctor Dalmau, Marc Thurley
Descriptive complexity of approximate counting CSPs. CSL (2013)
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) (2013)
Cong Wang, Andrei A. Bulatov
Inferring Attitude in Online Social Networks Based On Quadratic Correlation CoRR (2012)
Andrei A. Bulatov, Amir Hedayaty
Counting Problems and Clones of Functions. J. Multiple Valued Log. Soft Comput. 18 (2) (2012)
Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
Enumerating homomorphisms. J. Comput. Syst. Sci. 78 (2) (2012)
Andrei A. Bulatov, Dániel Marx
Constraint satisfaction parameterized by solution size CoRR (2012)
Andrei A. Bulatov, Amir Hedayaty
Galois correspondence for counting quantifiers CoRR (2012)
Cong Wang, Andrei A. Bulatov
Greedy Algorithms, Ordering of Variables, and d-degenerate Instances. ISMVL (2012)
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) (2012)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
Log-supermodular functions, functional clones and counting CSPs. STACS (2012)
Andrei A. Bulatov, Amir Hedayaty
Counting Predicates, Subset Surjective Functions, and Counting CSPs. ISMVL (2012)
Andrei A. Bulatov
Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12 (4) (2011)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
Log-supermodular functions, functional clones and counting CSPs CoRR (2011)
Andrei A. Bulatov
On the CSP Dichotomy Conjecture. CSR (2011)
Andrei A. Bulatov, Dániel Marx
Constraint Satisfaction Parameterized by Solution Size. ICALP (1) (2011)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
The complexity of weighted and unweighted #CSP CoRR (2010)
Andrei A. Bulatov, Dániel Marx
Constraint satisfaction problems and global cardinality constraints. Commun. ACM 53 (9) (2010)
Andrei A. Bulatov, Dániel Marx
The complexity of global cardinality constraints Log. Methods Comput. Sci. 6 (4) (2010)
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) (2009)
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) (2009)
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)
Andrei A. Bulatov
Counting Problems and Clones of Functions. ISMVL (2009)
Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
Enumerating Homomorphisms CoRR (2009)
Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
Enumerating Homomorphisms. STACS (2009)
Andrei A. Bulatov, Dániel Marx
The Complexity of Global Cardinality Constraints. LICS (2009)
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)
Albert Atserias, Andrei A. Bulatov, Anuj Dawar
Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410 (18) (2009)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
The Complexity of Weighted Boolean #CSP with Mixed Signs CoRR (2008)
Andrei A. Bulatov, Matthew Valeriote
Recent Results on the Algebraic Approach to the CSP. Complexity of Constraints (2008)
Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose
Dualities for Constraint Satisfaction Problems. Complexity of Constraints (2008)
Andrei A. Bulatov, Evgeny S. Skvortsov
Phase transition for Local Search on planted SAT CoRR (2008)
Andrei A. Bulatov
The Complexity of the Counting Constraint Satisfaction Problem. ICALP (1) (2008)
Andrei A. Bulatov
The complexity of the counting constraint satisfaction problem. Electron. Colloquium Comput. Complex. 14 (093) (2007)
Albert Atserias, Andrei A. Bulatov, Anuj Dawar
Affine Systems of Equations and Counting Infinitary Logic. ICALP (2007)
Albert Atserias, Andrei A. Bulatov, Víctor Dalmau
-Consistency. ICALP (2007)
Andrei A. Bulatov, Víctor Dalmau
Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput. 205 (5) (2007)
Andrei A. Bulatov, Hubie Chen, Víctor Dalmau
Learning intersection-closed classes with signatures. Theor. Comput. Sci. 382 (3) (2007)
Andrei A. Bulatov, Evgeny S. Skvortsov
Efficiency of Local Search. SAT (2006)
Andrei A. Bulatov, Víctor Dalmau
A Simple Algorithm for Mal'tsev Constraints. SIAM J. Comput. 36 (1) (2006)
Andrei A. Bulatov
A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53 (1) (2006)
Andrei A. Bulatov
H-Coloring dichotomy revisited. Theor. Comput. Sci. 349 (1) (2005)
Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34 (3) (2005)
Andrei A. Bulatov, Martin Grohe
The complexity of partition functions. Theor. Comput. Sci. 348 (2-3) (2005)
Andrei A. Bulatov, Martin Grohe
The Complexity of Partition Functions. ICALP (2004)
Andrei A. Bulatov, Hubie Chen, Víctor Dalmau
Learnability of Relatively Quantified Generalized Formulas. ALT (2004)
Andrei A. Bulatov
A Graph of a Relational Structure and Constraint Satisfaction Problems. LICS (2004)
Andrei A. Bulatov, Evgeny S. Skvortsov
Amalgams of Constraint Satisfaction Problems. IJCAI (2003)
Andrei A. Bulatov, Víctor Dalmau
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. FOCS (2003)
Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL (2003)
Andrei A. Bulatov, Pawel M. Idziak
Counting Mal'tsev clones on small sets. Discret. Math. 268 (1-3) (2003)
Andrei A. Bulatov
Tractable conservative Constraint Satisfaction Problems. LICS (2003)
Andrei A. Bulatov, Peter Jeavons
An Algebraic Approach to Multi-sorted Constraints. CP (2003)

Andrei A. Bulatov.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Andrei A. Bulatov