The Constraint Satisfaction Problem: Complexity and Approximability

With the resolution of the Feder-Vardi conjecture on finite-domain CSPs by Bulatov and Zhuk in 2017, the field has moved on to more generalizations of finite-domain decision CSPs. One of the main emerging areas is that of Promise CSPs (PCSPs), which are a huge generalization of CSPs.

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\mathrm{\Omega }(n/\log n)$ in the Polynomial Calculus (over fields of characteristic $\ne 2$) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovász-Schrijver proof system requires $n^{\delta }$ rounds to refute these formulas for some $\delta >0$. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

The combinatorial value of a CSP instance is a certain positive integer, which is equal to one iff the instance is satisfiable. In a joint work with Marcin Kozik we proved that a natural reduction amplifies the gap between value one and value strictly greater than one. I will talk about this result, its motivations, applications, recent developments (with Filip Bialas), and future directions.

In his beautiful result, Raghavendra gave a complete characterization of the inapproximability for every constraint satisfaction problem, assuming the Unique Games conjecture. This result however loses perfect completeness. In this talk, I will discuss the inapproximability of satisfiable linear equations over non-Abelian groups. Unlike Abelian groups, it is NP-complete to decide if a given system of linear equations over non-Abelian groups is satisfiable or not. We show tight NP-hardness results for approximately solving a satisfiable system of linear equations over non-Abelian groups. I will also discuss new techniques for characterizing the inapproximability of satisfiable CSPs.

Many natural classes of computational problems can be formulated as CSPs for first-order expansions of some base structure, such as . In this talk I will present methods how to transfer classification results for such classes from one base structure to another. This is particularly interesting if the base structure is a product structure, in which case one may hope to obtain the classification from the classifications of the factors.

Our results imply new classification results for CSPs that concern Allen’s Interval Algebra, the n-dimensional Block Algebra, and the Cardinal Direction Calculus and solve some open problems about these formalisms from 1999 and 2002.

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width.

In this talk, I will discuss our recent work on robust satisfaction algorithms for Promise CSPs, which are a vast generalization of CSPs. I will present robust SDP rounding algorithms under some general conditions, namely the existence of majority or alternating threshold polymorphisms. On the hardness front, I will prove that the lack of such polymorphisms makes the PCSP hard for a large class of symmetric Boolean predicates. Our method involves a novel method to argue SDP gaps via the absence of certain colorings of the sphere, with connections to sphere Ramsey theory.

In the development of the theory of Promise CSPs, it has become increasingly common to capture the structure of tractable classes of PCSPs through the existence of a minion homomorphism, where one maps a chosen minion into the polymorphisms of the particular PCSP. As the field of PCSPs is still quite young, only a handful of interesting minions are currently understood. In this talk, I will present some recently-discovered minions with interesting properties, including one that captures tractability according to the “exact” basic semi-definite program.

In this talk we consider the Ideal Membership Problem (IMP for short), in which we are given polynomials $f_0,f_1,\mathrm{\dots },f_k$ and the question is to decide whether $f_0$ belongs to the ideal generated by $f_1,\mathrm{\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 (SOS). In such applications the IMP usually 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 solution algorithm.

The first part of this paper follows the work of Mastrolilli [SODA 2019] who initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form CSP(G), that is, CSPs in which the type of constraints is limited to relations from a set G.

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. First, we introduce a variation of the IMP and based on this propose a unified framework, different from the celebrated Buchberger’s algorithm, to construct a bounded degree Groebner Basis. Our algorithm, combined with the universal algebraic techniques, leads to polynomial-time construction of Groebner Basis for many combinatorial problems.

In this talk I will give an overview of recent work concerning the relationship between levels of the Sherali-Adams hierarchy for CSP and the equivalence relation induced by the 1-dimensional Weisfeiler-Leman algorithm on the set of CSP instances. In particular, I will discuss how the feasibility of a linear program obtained using the Sherali-Adams method can be decomposed into three separate components, and how this fact can be used to infer results about solvability of CSPs by distributed algorithms. I will explain how these results can be extended to the more general framework of Promise Valued CSP, and discuss how the first level of the Sherali-Adams hierarchy is no longer equivalent to the Basic Linear Programming relaxation in this broader framework.

Traditional notions of algorithmic efficiency, such as that of polynomial time, permit each input to be read in its entirety. However, the modern necessity of performing computations on large bodies of data poses situations where inputs are so large that it is prohibitively expensive to fully read them. These situations motivate the study of algorithms that only read a part of each input. Property testing provides a framework wherein it is possible to present such algorithms.

In property testing, the input is typically read via random access queries, and an algorithm’s desideratum is to distinguish between inputs that satisfy a property and inputs that are $ϵ$-far from satisfying the property. Intuitively speaking, an object is called $ϵ$-far from satisfying a property if one needs to modify more than an $ϵ$-fraction of the object in order for it satisfy the property; the exact definition depends on the context. The restriction on the allowed inputs leads to the possibility of algorithms that do not read the entire input.

In this work, we utilize the perspective of property testing to consider the testability of relational database queries. A primary motivation is the desire to avoid reading an entire database to decide a property hereof. We focus on conjunctive queries, which are the most basic and heavily studied database queries. Each conjunctive query can be represented as a relational structure $𝐀$ such that deciding if the conjunctive query is satisfied by a relational structure $𝐁$ is equivalent to deciding if there exists a homomorphism from $𝐀$ to $𝐁$. We phrase our results in terms of homomorphisms. Precisely, we study, for each relational structure $𝐀$, the testability of homomorphism inadmissibility from $𝐀$. We consider algorithms that have oracle access to an input relational structure $𝐁$ and that distinguish, with high probability, the case where there is no homomorphism from $𝐀$ to $𝐁$, from the case where one needs to remove a constant fraction of tuples from $𝐁$ in order to suppress all such homomorphisms.

We provide a complete characterization of the structures $𝐀$ from which one can test homomorphism inadmissibility with one-sided error by making a constant number of queries to $𝐁$. Our characterization shows that homomorphism inadmissibility from $𝐀$ is constant-query testable with one-sided error if and only if the core of $𝐀$ is $\alpha$-acyclic. We also show that the injective version of the problem is constant-query testable with one-sided error if $𝐀$ is $\alpha$-acyclic; this result generalizes existing results for testing subgraph-freeness in the general graph model.

The Sherali-Adams linear programming hierarchy is a powerful algorithmic framework that is naturally applicable to the context of promise constraint satisfaction problems. This talk, based on recent joint work with Standa Živný, aims to show that the structure lying at the core of the hierarchy has a multilinear nature, as it essentially consists in a space of tensors enjoying certain increasingly tight symmetries. The geometry of this space allows then to establish non-solvability of the approximate graph coloring problem via constantly many rounds of Sherali-Adams. Besides this primary application, our tensorisation approach introduces a new tool to the study of various hierarchies of algorithmic relaxations for computational problems within (and, possibly, beyond) the context of constraint satisfaction. For example, both the algorithmic frameworks known as local consistency checking and “sum of squares” Lasserre hierarchy for the SDP relaxation can be naturally described geometrically through the tensorisation technique, by considering different spaces of tensors.

We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfies a certain structural condition implying that its algebraic closure-properties include weak near unanimity polymorphisms of all large arities. While this parallels the standard (non-promise) CSP theory, the method of proof is quite different and applies even to the regime of sublinear width. We also show that, in contrast with the CSP world, the presence of weak near unanimity polymorphisms of all large arities does not guarantee solvability in bounded width. The separating example is even solvable in the second level of the Sherali-Adams (SA) hierarchy of linear programming relaxations. This shows that, unlike for CSPs, linear programming can be stronger than bounded width. A direct application of these methods also show that the problem of q-coloring p-colorable graphs is not solvable in bounded or even sublinear width, for any two constants $p$ and $q$ such that $3\le p\le q$. Turning to algorithms, we note that Wigderson’s algorithm for coloring $3$-colorable graphs with $n$ vertices is implementable in width $4$. Indeed, by generalizing the method we see that, for any $ϵ>0$ smaller than $1/2$, the optimal width for solving the problem of $O(n^{ϵ})$-coloring $3$-colorable graphs with $n$ vertices lies between $n^{1-3ϵ}$ and $n^{1-2ϵ}$. The upper bound gives a simple exp$(\mathrm{\Theta }(n^{1-2ϵ}\log (n)))$-time algorithm that, asymptotically, beats the straightforward exp$(\mathrm{\Theta }(n^{1-ϵ}))$ bound that follows from partitioning the graph into $O(n^{ϵ})$ many independent parts each of size $O(n^{1-ϵ})$.

In this talk we give a brief introduction to the subject of Combinatorial Algebraic Topology, which lies at the crossroads of combinatorics, topology, and computation. A special emphasis is given to the family of the so-called Hom-complexes.

Given any two graphs $G$ and $H$, it is possible to construct a combinatorial cell complex (more precisely a prodsimplicial complex) whose set of vertices is the set of all graph homomorphisms from $G$ to $H$, and whose cellular structure reflects the commutativity relations within various groups of homomorphisms. We illuminate various structural properties of this family of cell complexes, especially with a view towards their recent applications to the complexity theory of CSPs.

Counting graph homomorphisms and its generalizations such as the Counting Constraint Satisfaction Problem (CSP), its variations, and counting problems in general have been intensively studied since the pioneering work of Valiant. While the complexity of exact counting of graph homomorphisms (Dyer and Greenhill, 2000) and the counting CSP (Bulatov, 2013, and Dyer and Richerby, 2013) is well understood, counting modulo some natural number has attracted considerable interest as well. In their 2015 paper Faben and Jerrum suggested a conjecture stating that counting homomorphisms to a fixed graph $H$ modulo a prime number is hard whenever it is hard to count exactly, unless $H$ has automorphisms of certain kind. In this talk we talk about this conjecture and how to prove it. As a part of this investigation we develop techniques that widen the spectrum of reductions available for modular counting and apply to the general CSP rather than being limited to graph homomorphisms.

Besides linear programming relaxations, one of the main strategies in proving the tractability of promise constraint satisfaction problems is to reduce them to tractable CSPs. In particular, PCSP($𝐀,𝐁$) is called finitely tractable, if there is a finite structure $𝐂$ such that there are homomorphisms $𝐀\to 𝐂\to 𝐁$ and CSP($𝐂$) is tractable. In this case every algorithm for CSP($𝐂$) also solves PCSP($𝐀,𝐁$). In this talk I will give an overview of known results on finitely tractable PCSPs and discuss some open questions.

I’ll present a new algorithm to refute, that is, efficiently find certificates of unsatisfiability, for smoothed instances of $k$-SAT and other CSPs. Smoothed instances are produced by starting with a worst-case instance and flipping each literal in every clause independently with a small constant probability. The “clause” structure in such instances is arbitrary and the only randomness is in the literal patterns. The trade-off between the density, i.e., the number of constraints in the instance, and the running time required by the algorithm matches (up to polylogarithmic factors density) the best known (and possibly sharp) trade-off for random $k$-SAT. As a corollary, we also obtain a simpler analysis for refuting random $k$-SAT formulas.

Our analysis inspires a new method that we call spectral double counting that we use to prove Feige’s 2008 conjecture on the extremal trade-off between the size of the hypergraph and its girth that generalizes the Moore bound on the girth of irregular graphs proved by Alon, Hoory, and Linial (2002). As a corollary, we obtain that smoothed instances of 3-SAT with arbitrary clause structure and $n^{1.4}$ ($\ll n^{1.5}$, the threshold for known efficient refutation) constraints admit polynomial-size certificates of unsatisfiability with appropriate generalization to all $k$-CSPs. This extends the celebrated work of Feige, Kim, and Ofek (2006) who proved a similar result for random 3-SAT. FKO’s proof uses a 2nd-moment-method based argument that strongly exploits the randomness of the clause structure. Our proof gives a simpler argument that extends to “worst-case” clause structures.

Taken together, our results show that smoothed instances with arbitrary clause structure and significantly less randomness enjoy the same thresholds for both refutation algorithms and certificates of unsatisfiability as random instances.

A PCSP is said to be first-order definable if there exists a first-order sentence that holds on all Yes-instances and does not hold on No-instances. I will prove that PCSP($𝐀,𝐁$) is first-order definable exactly when there exists a finite sandwich $𝐀\to 𝐂\to 𝐁$ where $𝐂$ has finite duality. Using similar tools, I will show how to give a sandwich-characterisation of PCSPs solvable by local consistency.

We consider CSPs over random $k$-uniform hypergraphs. Using the theory of smooth approximations, we can reduce the problem of finding an injective solution to such CSPs to a finite-domain CSP. On the other hand, surprisingly the problem of finding an arbitrary solution to such CSPs does not naturally reduce to a finite-domain CSP. We will present algorithmic techniques based on polymorphisms that allow us to reduce the latter problem to the aforementioned problem of finding an injective solution. This way, we confirm the Bodirsky-Pinsker conjecture for the random $k$-uniform hypergraphs for any $k$.

A linearly ordered (LO) $k$-colouring of an $r$-uniform hyper graph assigns an integer colour from $1$ to $k$ to each vertex of the hyper graph, such that every edge contains a unique maximum colour. We will discuss two results relating to LO colouring promise problems. First, we will show the relationships between the polymorhpism minions of LO $2$ vs LO $k$ colouring for all $k\ge 3$, and we use this to prove that LO $k$ vs LO $\mathrm{\ell }$ colouring is NP-hard for uniformity $r\ge l-k+4$. We will also discuss an algorithm that, if given an LO $2$-colourable $3$-uniform hypergraph, will find an LO $O(\sqrt{(n\log \log n}/\log n)$ colouring.

The promise CSP is a certain “structural approximation” variant of the CSP. The key difference from standard CSP is that the template consists of two structures $𝐀$ and $𝐁$, s.t., $𝐀$ maps homomorphically to $𝐁$. The search version of promise CSP can be formulated as: given an instance $𝐗$ of CSP($𝐀$) that is promised to have a solution, i.e., there is a homomorphism from $𝐗$ to $𝐀$, find a homomorphism from $𝐗$ to $𝐁$. For example, we could ask to find a 6 colouring of a graph that is promised to be 3 colourable. This promise CSP gained a lot of attention in recent years for a few reasons: it has substantial interactions with other variants of approximation, and it gives many interesting insights into the theory of classical CSPs.

In the tutorial I will give a brief overview of the basic abstract theory of promise CSPs with focus on several key concepts: gadget reductions, polymorphisms, minions, free structures, and their interactions with standard CSPs.

This is the first part of the tutorial on promise CSPs.

Approximate graph colouring is a prominent promise CSP, it asks to find a colouring using $k$ colours of a graph that is 3-colourable where $k>3$. It is a notorious open problem in computational complexity. We could also ask whether the problem gets easier if we strengthen the promise but insist on finding a 3-colouring. In the talk, we will discuss a method, based on topological ideas first used in graph colouring by Lovász, that shows that strengthening the promise does not make the problem easier (unless the promise implies that the graph is 2-colourable), and where these topological ideas might lead in classification of computational complexity of similar problems in the near future.

This is the second part of the tutorial on promise CSPs.

We give an overview of recent developments around the dichotomy conjecture for CSPs of infinite-domain structures such as the order of the rationals or the random graph. It was believed until recently that in the context of CSPs, the mathematical theory for those structures with an order (such as the order of the rationals) was quite different from those without an order (such as the random graph), and that in particular the latter were always solvable by a certain natural reduction to finite-domain CSPs, whereas the former can never be solved that way. We show that this dividing line between ordered and non-ordered structures does not provide this expected dichotomy of approaches, and that orders can appear out of nothing in unordered structures. As a consequence, this forces us to give up the project of always reducing “non-ordered” CSPs to finite-domain CSPs, and to take on the challenge of directly lifting Zhuk’s finite-domain algorithmic techniques to infinite-domain CSPs.

The NAE-SAT predicate (where NAE stands for not all equal) is a simple predicate which is 0 if all of its inputs are equal and 1 otherwise. For any fixed $k$, there is a 7/8 or better approximation algorithm for instances of MAX NAE-SAT where each clause has length exactly $k$. However, the approximability of MAX NAE-SAT with a mixture of different clause sizes is much less well understood. Before our work, it was an open problem whether or not there is a 7/8 approximation algorithm for MAX NAE-SAT where all clause lengths are allowed.

In this talk, I will prove that the approximation ratio for MAX NAE-SAT with clauses of lengths 3 and 5 is at most 0.8739 (assuming unique games is hard). I will then describe an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with clauses of lengths 3 and 5 which we conjecture gives a 0.8728-approximation. After describing this algorithm, I will describe how we found this algorithm, why we conjecture that it gives a 0.8728-approximation, and why it may well be the optimal approximation algorithm for almost satisfiable instances of MAX NAE-SAT with clauses of lengths 3 and 5.

In this tutorial, we will give an overview of existing and some recent results on approximating CSPs via the Sums of Squares hierarchy. We will also examine the role played by various notions of expansion, for proving both upper and lower bounds.

The Quantified Constraint Satisfaction Problem (QCSP) is the generalization of the Constraint Satisfaction problem (CSP) where we allow both existen- tial and universal quantifiers. Formally, the QCSP over a constraint language $\mathrm{\Gamma }$ is the problem to evaluate a sentence of the form

where $R_1,\mathrm{\dots },R_s$ are relations from $\mathrm{\Gamma }$. While CSP remains in NP for any $\mathrm{\Gamma }$, QCSP can be PSpace-hard, as witnessed by Quantified 3-Satisfiability or Quantified Graph 3-Colouring.

It turned out that there are no constraint languages whose QCSP complexity is in between PSpace and ${\mathrm{\Pi }}_2^p$. The proof is based on a natural reduction of a QCSP instance to an exponential size CSP instance. We show that, unless the problem is PSpace-hard, for any false instance there exists a polynomial part of the CSP instance without a solution, which immediately brings us to the ${\mathrm{\Pi }}_2^p$ complexity class. In the talk we will discuss the proof as well as a concrete constraint language whose QCSP is ${\mathrm{\Pi }}_2^p$-complete.