Andrei A. Bulatov

114 papers A* 22A 9B 5C 1Misc 2Journal 61Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Modular Counting over 3-Element and Conservative Domains. STACS Andrei A. Bulatov, Amirhossein Kazeminia
2025	J	`jnl`	Discrete Homotopy and Promise Constraint Satisfaction Problem. CoRR Arash Beikmohammadi, Andrei A. Bulatov
2025	A	`conf`	Modular Counting CSP: Reductions and Algorithms. STACS Amirhossein Kazeminia, Andrei A. Bulatov
2025	J	`jnl`	Modular Counting CSP: Reductions and Algorithms. CoRR Amirhossein Kazeminia, Andrei A. Bulatov
2025	J	`jnl`	Modular Counting over 3-Element and Conservative Domains. CoRR Andrei A. Bulatov, Amirhossein Kazeminia
2025	A*	`conf`	Satisfiability of Commutative vs. Non-Commutative CSPs. ICALP Andrei A. Bulatov, Stanislav Zivný
2024	J	`jnl`	Satisfiability of commutative vs. non-commutative CSPs. CoRR Andrei A. Bulatov, Stanislav Zivný
2022	A*	`conf`	Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution. AAAI Oleksii Omelchenko, Andrei A. Bulatov
2022	A*	`conf`	Complexity classification of counting graph homomorphisms modulo a prime number. STOC Andrei A. Bulatov, Amirhossein Kazeminia
2022	A*	`conf`	On the complexity of CSP-based ideal membership problems. STOC Andrei A. Bulatov, Akbar Rafiey
2022	A	`conf`	The Ideal Membership Problem and Abelian Groups. STACS Andrei A. Bulatov, Akbar Rafiey
2022	J	`jnl`	The Ideal Membership Problem and Abelian Groups. CoRR Andrei A. Bulatov, Akbar Rafiey
2021	J	`jnl`	Complexity classification of counting graph homomorphisms modulo a prime number. CoRR Andrei A. Bulatov, Amirhossein Kazeminia
2021	J	`jnl`	Satisfiability threshold for power law random 2-SAT in configuration model. Theor. Comput. Sci. Oleksii Omelchenko, Andrei A. Bulatov
2021	A*	`conf`	Symmetries and Complexity (Invited Talk). ICALP Andrei A. Bulatov
2020	J	`jnl`	A dichotomy theorem for nonuniform CSPs simplified. CoRR Andrei A. Bulatov
2020	J	`jnl`	Approximate Counting CSP Seen from the Other Side. ACM Trans. Comput. Theory Andrei A. Bulatov, Stanislav Zivný
2020	A*	`conf`	Counting Homomorphisms in Plain Exponential Time. ICALP Andrei A. Bulatov, Amineh Dadsetan
2020	J	`jnl`	Graphs of relational structures: restricted types. CoRR Andrei A. Bulatov
2020	J	`jnl`	Local structure of idempotent algebras I. CoRR Andrei A. Bulatov
2020	J	`jnl`	Local structure of idempotent algebras II. CoRR Andrei A. Bulatov
2020	J	`jnl`	On the Complexity of CSP-based Ideal Membership Problems. CoRR Andrei A. Bulatov, Akbar Rafiey
2019	A*	`conf`	A short story of the CSP dichotomy conjecture. LICS Andrei A. Bulatov
2019	B	`conf`	Approximate Counting CSP Seen from the Other Side. MFCS Andrei A. Bulatov, Stanislav Zivný
2019	J	`jnl`	Approximate counting CSP seen from the other side. CoRR Andrei A. Bulatov, Stanislav Zivný
2019	J	`jnl`	Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. Inf. Comput. Andrei A. Bulatov
2019	B	`conf`	Counting Homomorphisms Modulo a Prime Number. MFCS Amirhossein Kazeminia, Andrei A. Bulatov
2019	J	`jnl`	Counting Homomorphisms Modulo a Prime Number. CoRR Amirhossein Kazeminia, Andrei A. Bulatov
2019	A*	`conf`	Dismantlability, Connectedness, and Mixing in Relational Structures. ICALP Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, Benoît Larose
2019	A	`conf`	Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. SAT Oleksii Omelchenko, Andrei A. Bulatov
2019	J	`jnl`	Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. CoRR Oleksii Omelchenko, Andrei A. Bulatov
2018	C	`conf`	Constraint Satisfaction Problems: Complexity and Algorithms. LATA Andrei A. Bulatov
2018	J	`jnl`	Constraint satisfaction problems: complexity and algorithms. ACM SIGLOG News Andrei A. Bulatov
2018	J	`jnl`	Counting homomorphisms in plain exponential time. CoRR Amineh Dadsetan, Andrei A. Bulatov
2017	A*	`conf`	A Dichotomy Theorem for Nonuniform CSPs. FOCS Andrei A. Bulatov
2017	J	`jnl`	A dichotomy theorem for nonuniform CSPs. CoRR Andrei A. Bulatov
2017	J	`jnl`	Constraint Satisfaction Problems over semilattice block Mal'tsev algebras. CoRR Andrei A. Bulatov
2017	A*	`conf`	Constraint satisfaction problems over semilattice block Mal'tsev algebras. LICS Andrei A. Bulatov
2017	J	`jnl`	Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? Electron. J. Comb. Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev
2017	J	`jnl`	Preface. Theory Comput. Syst. Andrei A. Bulatov, Edward A. Hirsch, Jean-Éric Pin
2016	J	`jnl`	Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci. Andrei A. Bulatov
2016	J	`jnl`	Functional Clones and Expressibility of Partition Functions. CoRR Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
2016	J	`jnl`	Graphs of finite algebras, edges, and connectivity. CoRR Andrei A. Bulatov
2016	A*	`conf`	Graphs of relational structures: restricted types. LICS Andrei A. Bulatov
2016	J	`jnl`	Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups? CoRR Andrei A. Bulatov, Olga Karpova, Arseny M. Shur, Konstantin Startsev
2015	J	`jnl`	Galois Correspondence for Counting Quantifiers. J. Multiple Valued Log. Soft Comput. Andrei A. Bulatov, Amir Hedayaty
2015	—	`conf`	Phase Transition for Local Search on Planted SAT. MFCS (2) Andrei A. Bulatov, Evgeny S. Skvortsov
2015	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx
2014	A	`conf`	Approximating Highly Satisfiable Random 2-SAT. SAT Andrei A. Bulatov, Cong Wang
2014	J	`jnl`	Conservative constraint satisfaction re-revisited. CoRR Andrei A. Bulatov
2014	J	`jnl`	Constraint Satisfaction Parameterized by Solution Size. SIAM J. Comput. Andrei A. Bulatov, Dániel Marx
2014	—	`conf`	Inferring Attitude in Online Social Networks Based on Quadratic Correlation. PAKDD (1) Cong Wang, Andrei A. Bulatov
2013	—	`conf`	Boolean Max-Co-Clones. ISMVL Andrei A. Bulatov
2013	Misc	`ed.`	Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings CSR Andrei A. Bulatov, Arseny M. Shur
2013	B	`conf`	Descriptive complexity of approximate counting CSPs. CSL Andrei A. Bulatov, Víctor Dalmau, Marc Thurley
2013	J	`jnl`	The complexity of the counting constraint satisfaction problem. J. ACM Andrei A. Bulatov
2013	J	`jnl`	The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
2012	J	`jnl`	Constraint satisfaction parameterized by solution size CoRR Andrei A. Bulatov, Dániel Marx
2012	—	`conf`	Counting Predicates, Subset Surjective Functions, and Counting CSPs. ISMVL Andrei A. Bulatov, Amir Hedayaty
2012	J	`jnl`	Counting Problems and Clones of Functions. J. Multiple Valued Log. Soft Comput. Andrei A. Bulatov, Amir Hedayaty
2012	J	`jnl`	Enumerating homomorphisms. J. Comput. Syst. Sci. Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
2012	J	`jnl`	Galois correspondence for counting quantifiers CoRR Andrei A. Bulatov, Amir Hedayaty
2012	—	`conf`	Greedy Algorithms, Ordering of Variables, and d-degenerate Instances. ISMVL Cong Wang, Andrei A. Bulatov
2012	J	`jnl`	Inferring Attitude in Online Social Networks Based On Quadratic Correlation CoRR Cong Wang, Andrei A. Bulatov
2012	A	`conf`	Log-supermodular functions, functional clones and counting CSPs. STACS Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
2012	J	`jnl`	The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
2011	J	`jnl`	Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. Andrei A. Bulatov
2011	—	`conf`	Constraint Satisfaction Parameterized by Solution Size. ICALP (1) Andrei A. Bulatov, Dániel Marx
2011	J	`jnl`	Log-supermodular functions, functional clones and counting CSPs CoRR Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
2011	Misc	`conf`	On the CSP Dichotomy Conjecture. CSR Andrei A. Bulatov
2010	J	`jnl`	Constraint satisfaction problems and global cardinality constraints. Commun. ACM Andrei A. Bulatov, Dániel Marx
2010	J	`jnl`	The complexity of global cardinality constraints Log. Methods Comput. Sci. Andrei A. Bulatov, Dániel Marx
2010	J	`jnl`	The complexity of weighted and unweighted #CSP CoRR Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
2009	—	`conf`	09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	—	`conf`	09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	J	`jnl`	Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. Albert Atserias, Andrei A. Bulatov, Anuj Dawar
2009	—	`conf`	Counting Problems and Clones of Functions. ISMVL Andrei A. Bulatov
2009	J	`jnl`	Enumerating Homomorphisms CoRR Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
2009	A	`conf`	Enumerating Homomorphisms. STACS Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx
2009	A*	`conf`	The Complexity of Global Cardinality Constraints. LICS Andrei A. Bulatov, Dániel Marx
2009	—	`ed.`	The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009 The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	J	`jnl`	The complexity of constraint satisfaction games and QCSP. Inf. Comput. Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin
2009	J	`jnl`	The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
2008	—	`conf`	Dualities for Constraint Satisfaction Problems. Complexity of Constraints Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose
2008	J	`jnl`	Phase transition for Local Search on planted SAT CoRR Andrei A. Bulatov, Evgeny S. Skvortsov
2008	—	`conf`	Recent Results on the Algebraic Approach to the CSP. Complexity of Constraints Andrei A. Bulatov, Matthew Valeriote
2008	J	`jnl`	The Complexity of Weighted Boolean #CSP with Mixed Signs CoRR Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
2008	—	`conf`	The Complexity of the Counting Constraint Satisfaction Problem. ICALP (1) Andrei A. Bulatov
2007	A*	`conf`	Affine Systems of Equations and Counting Infinitary Logic. ICALP Albert Atserias, Andrei A. Bulatov, Anuj Dawar
2007	J	`jnl`	Learning intersection-closed classes with signatures. Theor. Comput. Sci. Andrei A. Bulatov, Hubie Chen, Víctor Dalmau
2007	A*	`conf`	On the Power of ICALP Albert Atserias, Andrei A. Bulatov, Víctor Dalmau
2007	J	`jnl`	The complexity of the counting constraint satisfaction problem. Electron. Colloquium Comput. Complex. Andrei A. Bulatov
2007	J	`jnl`	Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput. Andrei A. Bulatov, Víctor Dalmau
2006	J	`jnl`	A Simple Algorithm for Mal'tsev Constraints. SIAM J. Comput. Andrei A. Bulatov, Víctor Dalmau
2006	J	`jnl`	A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM Andrei A. Bulatov
2006	A	`conf`	Efficiency of Local Search. SAT Andrei A. Bulatov, Evgeny S. Skvortsov
2005	J	`jnl`	Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
2005	J	`jnl`	H-Coloring dichotomy revisited. Theor. Comput. Sci. Andrei A. Bulatov
2005	J	`jnl`	The complexity of partition functions. Theor. Comput. Sci. Andrei A. Bulatov, Martin Grohe
2004	A*	`conf`	A Graph of a Relational Structure and Constraint Satisfaction Problems. LICS Andrei A. Bulatov
2004	B	`conf`	Learnability of Relatively Quantified Generalized Formulas. ALT Andrei A. Bulatov, Hubie Chen, Víctor Dalmau
2004	A*	`conf`	The Complexity of Partition Functions. ICALP Andrei A. Bulatov, Martin Grohe
2003	A*	`conf`	Amalgams of Constraint Satisfaction Problems. IJCAI Andrei A. Bulatov, Evgeny S. Skvortsov
2003	A	`conf`	An Algebraic Approach to Multi-sorted Constraints. CP Andrei A. Bulatov, Peter Jeavons
2003	J	`jnl`	Counting Mal'tsev clones on small sets. Discret. Math. Andrei A. Bulatov, Pawel M. Idziak
2003	—	`conf`	Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons
2003	B	`conf`	Quantified Constraints: Algorithms and Complexity. CSL Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
2003	A*	`conf`	Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. FOCS Andrei A. Bulatov, Víctor Dalmau
2003	A*	`conf`	Tractable conservative Constraint Satisfaction Problems. LICS Andrei A. Bulatov
2002	A*	`conf`	A Dichotomy Theorem for Constraints on a Three-Element Set. FOCS Andrei A. Bulatov
2002	J	`jnl`	Mal'tsev constraints are tractable Electron. Colloquium Comput. Complex. Andrei A. Bulatov
2002	J	`jnl`	Tractable Constraint Satisfaction Problems on a 3-element set Electron. Colloquium Comput. Complex. Andrei A. Bulatov
2001	A*	`conf`	The complexity of maximal constraint languages. STOC Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
2000	A*	`conf`	Constraint Satisfaction Problems and Finite Algebras. ICALP Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons