Andrei A. Bulatov

AAAI Conference 2022 Conference Paper

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

• Oleksii Omelchenko
• Andrei A. Bulatov

MAX k-SAT is one of the archetypal NP-hard problems. Its variation called random MAX k-SAT problem was introduced in order to understand how hard it is to solve instances of the problem on average. The most common model to sample random instances is the uniform model, which has received a large amount of attention. However, the uniform model often fails to capture important structural properties we observe in the real-world instances. To address these limitations, a more general (in a certain sense) model has been proposed, the configuration model, which is able to produce instances with an arbitrary distribution of variables’ degrees, and so can simulate biases in instances appearing in various applications. Our overall goal is to expand the theory built around the uniform model to the more general configuration model for a wide range of degree distributions. This includes locating satisfiability thresholds and analysing the performance of the standard heuristics applied to instances sampled from the configuration model. In this paper we analyse the performance of the pure literal elimination rule. We provide an equation that given an underlying degree distribution gives the number of clauses the pure literal elimination rule satisfies w. h. p. We also show how the distribution of variable degrees changes over time as the algorithm is being executed.

STOC Conference 2022 Conference Paper

Complexity classification of counting graph homomorphisms modulo a prime number

• Andrei A. Bulatov
• Amirhossein Kazeminia

STOC Conference 2022 Conference Paper

On the complexity of CSP-based ideal membership problems

• Andrei A. Bulatov
• Akbar Rafiey

TCS Journal 2021 Journal Article

Satisfiability threshold for power law random 2-SAT in configuration model

• Oleksii Omelchenko
• Andrei A. Bulatov

We study Random 2-SAT problem, in which 2-CNFs are sampled from a wide range of non-uniform distributions, including heavy-tailed using random model that is quite different from the standard uniform Random 2-SAT. This model of random SAT is the so-called configuration model, given by a distribution ξ for the degree (or the number of occurrences) of each variable. To generate a formula the degree of each variable is sampled from ξ, generating several clones of the variable. Then 2-clauses are created by choosing a random partitioning 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 ξ. More precisely, we assume that ξ is such that its right tail F ξ ( x ) satisfies the conditions W ℓ − α ≤ F ξ ( ℓ ) ≤ V ℓ − α for some constants V, W. The main goal is to study the satisfiability threshold phenomenon, and we show that the threshold exists and is determined by a simple relation between the first and second moments of ξ.

MFCS Conference 2019 Conference Paper

Approximate Counting CSP Seen from the Other Side

• Andrei A. Bulatov
• Stanislav Zivný

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

MFCS Conference 2019 Conference Paper

Counting Homomorphisms Modulo a Prime Number

• Amirhossein Kazeminia
• Andrei A. Bulatov

Counting problems in general and counting graph homomorphisms in particular have numerous applications in combinatorics, computer science, statistical physics, and elsewhere. One of the most well studied problems in this area is #GraphHom(H) - the problem of finding the number of homomorphisms from a given graph G to the graph H. Not only the complexity of this basic problem is known, but also of its many variants for digraphs, more general relational structures, graphs with weights, and others. In this paper we consider a modification of #GraphHom(H), the #_{p}GraphHom(H) problem, p a prime number: Given a graph G, find the number of homomorphisms from G to H modulo p. In a series of papers Faben and Jerrum, and Göbel et al. determined the complexity of #_{2}GraphHom(H) in the case H (or, in fact, a certain graph derived from H) is square-free, that is, does not contain a 4-cycle. Also, Göbel et al. found the complexity of #_{p}GraphHom(H) when H is a tree for an arbitrary prime p. Here we extend the above result to show that the #_{p}GraphHom(H) problem is #_{p}P-hard whenever the derived graph associated with H is square-free and is not a star, which completely classifies the complexity of #_{p}GraphHom(H) for square-free graphs H.

SAT Conference 2019 Conference Paper

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

• Oleksii Omelchenko
• Andrei A. Bulatov

Abstract 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 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 \).

FOCS Conference 2017 Conference Paper

A Dichotomy Theorem for Nonuniform CSPs

• Andrei A. Bulatov

In a non-uniform Constraint Satisfaction problem CSP(Γ), where Γ is a set of relations on a unite set A, the goal is to und an assignment of values to variables subject to constraints imposed on speciued sets of variables using the relations from Γ. The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language Γ the problem CSP(Γ) is either solvable in polynomial time or is NP-complete. It was proposed by Feder and Vardi in their seminal 1993 paper. In this paper we confirm the Dichotomy Conjecture.

SAT Conference 2014 Conference Paper

Approximating Highly Satisfiable Random 2-SAT

• Andrei A. Bulatov
• Cong Wang 0002

Abstract In this paper we introduce two distributions for the Max-2-SAT problem similar to the uniform distribution of satisfiable CNFs and the planted distribution for the decision version of SAT. In both cases there is a parameter p, \(0\le p\le \frac14d\), such that formulas chosen according to both distributions are p -satisfiable, that is, at least \((\frac34d+p)n\) clauses can be satisfied. In the planted distribution this happens for a fixed assignment, while for the p -satisfiable distribution formulas are chosen uniformly from the set of all p -satisfiable formulas. Following Coja-Oghlan, Krivelevich, and Vilenchik (2007) we establish a connection between the probabilities of events under the two distributions. Then we consider the case when p is sufficiently large, and. We present an algorithm that in the case of the planted distribution for any with high probability finds an assignment satisfying at least clauses. For the p -satisfiable distribution for every d there is (which is a polynomial in d of degree depending on ) such that the algorithm with high probability finds an assignment satisfying at least clauses. It does not seem this algorithm can be converted into an expected polynomial time algorithm finding a p -satisfying assignment. Also we use the connection between the planted and uniform p -satisfiable distributions to evaluate the number of clauses satisfiable in a random (not p -satisfiable) 2-CNF. We find the expectation of this number, but do not improve the existing concentration results.

CSL Conference 2013 Conference Paper

Descriptive complexity of approximate counting CSPs

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

Motivated by Fagin's characterization of NP, Saluja et al. have introduced a logic based frame- work for expressing counting problems. In this setting, a counting problem (seen as a mapping C from structures to non-negative integers) is `defined’ by a first-order sentence phi if for every instance A of the problem, the number of possible satisfying assignments of the variables of phi in A is equal to C(A). The logic RHPI_1 has been introduced by Dyer et al. in their study of the counting complexity class #BIS. The interest in the class #BIS stems from the fact that, it is quite plausible that the problems in #BIS are not #P-hard, nor they admit a fully polynomial randomized approximation scheme. In the present paper we investigate which counting constraint satisfaction problems #CSP(H) are definable in the monotone fragment of RHPI_1. We prove that #CSP(H) is definable in monotone RHPI_1 whenever H is invariant under meet and join operations of a distributive lattice. We prove that the converse also holds if H contains the equality relation. We also prove similar results for counting CSPs expressible by linear Datalog. The results in this case are very similar to those for monotone RHPI1, with the addition that H has, additionally, \top (the greatest element of the lattice) as a polymorphism.

SAT Conference 2006 Conference Paper

Efficiency of Local Search

• Andrei A. Bulatov
• Evgeny S. Skvortsov

Abstract The Local Search algorithm is one of the simplest heuristic algothms for solving the MAX-SAT problem. The goal of this paper is to estimate the relative error produced by this algorithm being applied to random 3-CNFs with fixed density \(\varrho\). We prove that, for any \(\varrho\), there is a constant c such that a weakened version of Local Search that we call One-Pass Local Search almost surely outputs an assignment containing cn + o ( n ) unsatisfied clauses. Then using a certain assumtion we also show this for Local Search. Although the assumption remains unproved the results well matches experiments.

TCS Journal 2005 Journal Article

H-Coloring dichotomy revisited

• Andrei A. Bulatov

The H-Coloring problem can be expressed as a particular case of the constraint satisfaction problem (CSP) whose computational complexity has been intensively studied under various approaches in the last several years. We show that the dichotomy theorem proved by Hell and Nešetřil [On the complexity of H-coloring, J. Combin. Theory Ser. B 48 (1990) 92–110] for the complexity of the H-Coloring problem for undirected graphs can be obtained using general methods for studying CSP, and that the criterion distinguishing the tractable cases of the H-Coloring problem agrees with that conjectured in [A. A. Bulatov, P. G. Jeavons, A. A. Krokhin, Constraint satisfaction problems and finite algebras, in: Proc. 27th Internat. Colloq. on Automata, Languages and Programming—ICALP’00, Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 272–282] for the complexity of the general CSP.

IJCAI Conference 2003 Conference Paper

Amalgams of Constraint Satisfaction Problems

• Andrei A. Bulatov
• Eugeny S. Skvortsov

Many of standard practical techniques of solving constraint satisfaction problems use various decomposition methods to represent a problem as a combination of smaller ones. We study a general method of decomposing constraint satisfaction problems in which every constraint is represented as a disjunction of two or more simpler constraints defined, possibly, on smaller sets of values. We call a problem an amalgam if it can be decomposed in this way. Some particular cases of this construction have been considered in [Cohen et a/. , 1997; 2000b; 2000al including amalgams of problems with disjoint sets of values, and amalgams of independent problems. In this paper, we concentrate on constraint classes determined by relational clones, and study amalgams of such classes in the general case of arbitrary finite sets of values. We completely characterise amalgams of this form solvable in polynomial time and provide efficient algorithms.

CSL Conference 2003 Conference Paper

Quantified Constraints: Algorithms and Complexity

• Ferdinand Börner
• Andrei A. Bulatov
• Peter Jeavons 0001
• Andrei A. Krokhin

Abstract The standard constraint satisfaction problem over an arbitrary finite domain can be expressed as follows: given a first-order sentence consisting of a conjunction of predicates, where all of the variables are existentially quantified, determine whether the sentence is true. This problem can be parameterized by the set of allowed constraint predicates. With each predicate, one can associate certain predicate-preserving operations, called polymorphisms, and the complexity of the parameterized problem is known to be determined by the polymorphisms of the allowed predicates. In this paper we consider a more general framework for constraint satisfaction problems which allows arbitrary quantifiers over constrained variables, rather than just existential quantifiers. We show that the complexity of such extended problems is determined by the surjective polymorphisms of the constraint predicates. We give examples to illustrate how this result can be used to identify tractable and intractable cases for the quantified constraint satisfaction problem over arbitrary finite domains.

FOCS Conference 2003 Conference Paper

Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem

• Andrei A. Bulatov
• Víctor Dalmau

The Counting Constraint Satisfaction Problem (#CSP) over a finite domain can be expressed as follows: given a first-order formula consisting of a conjunction of predicates, determine the number of satisfying assignments to the formula. #CSP can be parametrized by the set of allowed constraint predicates. In this paper we start a systematic study of subclasses of #CSP restricted in this way. The ultimate goal of this investigation is to distinguish those restricted subclasses of #CSP which are tractable, i. e. solvable in polynomial time, from those which are not. We show that the complexity of any restricted #CSP class on a finite domain can be deduced from the properties of polymorphisms of the allowed constraints, similar to that for the decision CSP. Then we prove that if a subclass of the #CSP is tractable, then constraints allowed by the class satisfy some very restrictive condition: it has to have a Mal'tsev polymorphism, that is a ternary operation m(x, y, z) such that m(x, y, y) = m(y, y, x) = x. This condition uniformly explains all existing complexity results for particular cases of #CSP, and allows us to obtain new results and to conjecture a criterion distinguishing tractable counting CSPs. We also obtain a dichotomy theorem for the complexity of #CSP with a 3-element domain and give new simpler proofs of the dichotomy results for the problem of counting graph homomorphisms.

FOCS Conference 2002 Conference Paper

A Dichotomy Theorem for Constraints on a Three-Element Set

• Andrei A. Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on the possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate those subclasses of the CSP which are tractable, from those which remain NP-complete. In 1978 Schaefer gave an exhaustive solution of this problem for the CSP on a 2-element domain. In this paper we generalise this result to a classification of the complexity of CSPs on a 3-element domain. The main result states that every subclass of the CSP defined by a set of allowed constraints is either tractable or NP-complete, and the criterion separating them is that conjectured by Bulatov et al. (2001). We also exhibit a polynomial time algorithm which, for a given set of allowed constraints, determines whether if this set gives rise to a tractable problem class. To obtain the main result and the algorithm we extensively use the algebraic technique for the CSP developed by Jeavons (1998) and Bulatov et al.

STOC Conference 2001 Conference Paper

The complexity of maximal constraint languages

• Andrei A. Bulatov
• Andrei A. Krokhin
• Peter Jeavons 0001