ABAndrei Bulatov

Andrei Bulatov

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Andrei Bulatov has a total of 18 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

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

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

    This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend parts of the three approaches that have been developed to study the CSP over finite templates - absorption theory that was used to characterize CSPs solvable by local consistency methods (JACM'14), and Bulatov's and Zhuk's theories that were used for two independent proofs of the CSP Dichotomy Theorem (FOCS'17, JACM'20). As the first contribution we present an elementary theorem about primitive positive definability and use it to obtain the starting points of Bulatov's and Zhuk's proofs as corollaries. As the second contribution we propose and initiate a systematic study of minimal Taylor algebras. This class of algebras is broad enough so that it suffices to verify the CSP Dichotomy Theorem on this class only, but still is unusually well behaved. In particular, many concepts from the three approaches coincide in the class, which is in striking contrast with the general setting. We believe that the theory initiated in this paper will eventually result in a simple and more natural proof of the Dichotomy Theorem that employs a simpler and more efficient algorithm, and will help in attacking complexity questions in other CSP-related problems.

  • Open Access

    On the Complexity of CSP-based Ideal Membership Problems

    by Andrei A. Bulatov, Akbar Rafiey

    In this paper we consider the Ideal Membership Problem (IMP for short), in which we are given real polynomials $f_0,f_1,\dots, f_k$ and the question is to decide whether $f_0$ belongs to the ideal generated by $f_1,\dots,f_k$. In the more stringent version the task is also to find a proof of this fact. The IMP underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. In the majority of such applications the IMP involves so called combinatorial ideals that arise from a variety of discrete combinatorial problems. This restriction makes the IMP significantly easier and in some cases allows for an efficient algorithm to solve it. The first part of this paper follows the work of Mastrolilli [SODA'19] who initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form $CSP(\Gamma)$, that is, CSPs in which the type of constraints is limited to relations from a set $\Gamma$. We show that many CSP techniques can be translated to IMPs thus allowing us to significantly improve the methods of studying the complexity of the IMP. We also develop universal algebraic techniques for the IMP that have been so useful in the study of the CSP. This allows us to prove a general necessary condition for the tractability of the IMP, and three sufficient ones. The sufficient conditions include IMPs arising from systems of linear equations over $GF(p)$, $p$ prime, and also some conditions defined through special kinds of polymorphisms. Our work has several consequences and applications in terms of bit complexity of sum-of-squares (SOS) proofs and their automatizability, and studying (construction of) theta bodies of combinatorial problems.

  • Open Access

    Dismantlability, connectedness, and mixing in relational structures

    by Raimundo Briceño, Andrei Bulatov, Victor Dalmau, Benoit Larose

    The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.

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

    by Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Živný


  • Open Access

    Approximate counting CSP seen from the other side

    by Andrei A. Bulatov, Stanislav Zivny

    In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP($\mathcal{C}$,-), in which the goal is, given a relational structure $\mathbf{A}$ from a class $\mathcal{C}$ of structures and an arbitrary structure $\mathbf{B}$, to find the number of homomorphisms from $\mathbf{A}$ to $\mathbf{B}$. Flum and Grohe showed that #CSP($\mathcal{C}$,-) is solvable in polynomial time if $\mathcal{C}$ has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if $\mathcal{C}$ is a recursively enumerable class of relational structures of bounded arity, then assuming FPT $\neq$ #W[1], there are no other cases of #CSP($\mathcal{C}$,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT $\neq$ W[1] (under randomised parametrised reductions) and for $\mathcal{C}$ satisfying certain general conditions, #CSP($\mathcal{C}$,-) is not solvable even approximately for $\mathcal{C}$ of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP($\mathcal{C}$,-). In particular, our condition generalises the case when $\mathcal{C}$ is closed under taking minors.

  • Open Access

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

    by Oleksii Omelchenko, Andrei A. Bulatov

    The Random Satisfiability problem has been intensively studied for decades. For a number of reasons the focus of this study has mostly been on the model, in which instances are sampled uniformly at random from a set of formulas satisfying some clear conditions, such as fixed density or the probability of a clause to occur. However, some non-uniform distributions are also of considerable interest. In this paper we consider Random 2-SAT problems, in which instances are sampled from a wide range of non-uniform distributions. The model of random SAT we choose is the so-called configuration model, given by a distribution $\xi$ for the degree (or the number of occurrences) of each variable. Then to generate a formula the degree of each variable is sampled from $\xi$, generating several \emph{clones} of the variable. Then 2-clauses are created by choosing a random paritioning into 2-element sets on the set of clones and assigning the polarity of literals at random. Here we consider the random 2-SAT problem in the configuration model for power-law-like distributions $\xi$. More precisely, we assume that $\xi$ is such that its right tail $F_{\xi}(x)$ satisfies the conditions $W\ell^{-\alpha}\le F_{\xi}(\ell)\le V\ell^{-\alpha}$ for some constants $V,W$. The main goal is to study the satisfiability threshold phenomenon depending on the parameters $\alpha,V,W$. We show that a satisfiability threshold exists and is determined by a simple relation between the first and second moments of $\xi$.

  • Open Access

    Concentration inequalities for sums of random variables, each having power bounded tails

    by Oleksii Omelchenko, Andrei A. Bulatov

    In this work we present concentration inequalities for the sum $S_n$ of independent integer-valued not necessary indentically distributed random variables, where each variable has tail function that can be bounded by some power function with exponent $-\alpha$. We show that when $0<\alpha\leq 1$, then the sum does not have finite expectation, however, with high probability we have that $|S_n|=O\left(n^{1/\alpha}\right)$. When $\alpha>1$, then the sum $S_n$ is concentrated around its mean. Since the r.vs. that constitute the sum has tails, which can be bounded by some power function, it follows that results of this paper are applicable to a wide range of different distributions, including the exponentially decaying ones.

  • Open Access

    The Subpower Membership Problem for Finite Algebras with Cube Terms

    by Andrei Bulatov, Peter Mayr, Ágnes Szendrei

    The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra. We consider a variant of this problem, which is motivated by recent progress in the Constraint Satisfaction Problem, and is often referred to as the Subpower Membership Problem (SMP). In the SMP we are given a set of tuples in a direct product of algebras from a fixed finite set $\mathcal{K}$ of finite algebras, and are asked whether or not a given tuple belongs to the subalgebra of the direct product generated by a given set. Our main result is that the subpower membership problem SMP($\mathcal{K}$) is in P if $\mathcal{K}$ is a finite set of finite algebras with a cube term, provided $\mathcal{K}$ is contained in a residually small variety. We also prove that for any finite set of finite algebras $\mathcal{K}$ in a variety with a cube term, each one of the problems SMP($\mathcal{K}$), SMP($\mathbb{HS} \mathcal{K}$), and finding compact representations for subpowers in $\mathcal{K}$, is polynomial time reducible to any of the others, and the first two lie in NP.