SDPs and Robust Satisfiability of Promise CSP

SDPs and Robust Satisfiability of Promise CSP, Discrete Analysis 2025:14, 80 pp.

A constraint satisfaction problem, or CSP, is a problem where one has a set of variables $x_1,\dots,x_n$ that live in some set, together with a collection of constraints, and the task is to determine whether the constraints can be simultaneously satisfied. Some well known examples are $k$-SAT, where the variables live in $\{0,1\}$ and each constraint is a disjunction of $k$ conditions of the form $x_i=0$ or $x_i=1$, and $k$-LIN, where the variables live in $\mathbb F_2$ and each constraint is a linear equation over $\mathbb F_2$ in $k$ of the variables. The latter can be solved in polynomial time by Gaussian elimination, whereas the former has a polynomial-time algorithm when $k=2$ and is NP-complete for $k\geq 3$.

A small variant of this set-up changes the hardness of the problems in interesting ways. Suppose that you are given $m$ linear equations in $n$ variables, together with a guarantee that at least 99% of them can be simultaneously satisfied. Is there an efficient algorithm to find an assignment to the variables that satisfies at least 90% of them? An algorithm that can do this (with 99% replaced by $1-\epsilon$ and 90% replaced by $1-f(\epsilon)$ with $f(\epsilon)$ tending to 0 with $\epsilon$) is called a robust satisfaction algorithm. If one knew which of the equations were among the 99%, then this would reduce to linear algebra again, but one does not, and this turns out to make the problem hard: a result of Haståd shows that for every $\epsilon,\delta>0$ it is NP-hard to find an assignment of the variables that satisfies more than a fraction $1/2+\delta$ of the equations in an instance of 3-LIN, even if a fraction $1-\epsilon$ of the equations can be simultaneously satisfied. Thus, 3-LIN is a long way from having a robust satisfaction algorithm.

In general, natural CSP problems appear to obey a dichotomy: either they have polynomial-time algorithms or they are NP-hard. A major theme of current research is to understand this phenomenon, and in particular to identify the features of CSPs that determine whether they belong to the easy category or the hard category.

There have been some remarkable successes in this direction. In particular, in the case of robust satisfaction algorithms, there is a complete understanding of which CSPs have them. To understand this class, it is helpful to look at 2-SAT. Each condition here can be thought of as a pair of implications, one the contrapositive of the other: for example, the condition $x_1=1\vee x_2=1$ can be thought of as the pair of implications $\neg x_1\implies x_2$ and $\neg x_2\implies x_1$. This allows for a “local” algorithm that works as follows. Start by choosing a value for $x_1$ and iteratively explore all its implications. If at any stage you end up with a contradiction, such as deducing that $x_1$ has the opposite value, then restart the process with $x_1$ taking the opposite value. If no contradiction is reached, keep going until no more values are forced. If there are still unassigned values, then choose an unassigned variable and repeat the process. It is not hard to show that if the instance of 2-SAT is satisfiable, this procedure will yield a satisfying assignment in polynomial time.

What makes it “local”, or of “bounded width” is, roughly speaking, that at any one stage of the process one can forget about all but a bounded number (in this case 3) of the variables. This idea can be made formal in various different equivalent ways, and it turns out to characterize CSPs with efficient robust satisfaction algorithms: very roughly indeed, a CSP has an efficient robust satisfaction algorithm if and only if there is an algorithm that propagates values of candidate solutions in something like the local way that the above algorithm for 2-SAT does. For example, 3-LIN is not of bounded width in this sense – because there are three variables in each equation, knowing one of them does not force the values of the other two, so one has to keep track of many values at a time – and this in some sense explains why it does not have a robust satisfaction algorithm.

For the problems on the easy side such as 2-SAT, one cannot use the local propagation approach described above to produce a robust satisfaction algorithm, for the simple reason that if not all the constraints need to be satisfied, then no move is forced and the propagation does not occur. What one can do instead, it turns out, is consider a relaxation of the problem, solve the relaxation by semidefinite programming, and round the answer to an integer solution. Of course, since such an algorithm is very different from a local-propagation algorithm, proving the characterization above is not at all trivial: it relies in a fascinating way on an analysis of the underlying symmetries of the set of solutions to the CSP.

The object of this paper is to extend some of the theory that has worked so successfully for CSPs to problems known as promise CSPs, or PCSPs. Here one has not one but two sets of constraints, a “strong” set and a “weak” set. In this context, a robust satisfaction algorithm is an algorithm that finds an assignment that satisfies almost all of the weak constraints given that almost all of the strong constraints can be simultaneously satisfied. For example, one might try to find a 7-colouring of a graph that is almost a proper colouring (that is, only a tiny fraction of the edges are not properly coloured) given that there is an almost proper 3-colouring of the same graph.

Like traditional CSPs, PCSPs arise naturally in many contexts and have been extensively studied. The authors of this paper make a conjecture about which PSCPs have robust satisfaction algorithms, and take several steps towards proving their conjecture. In particular, they identify a class of PCSPs for which the SDP rounding approach works, again connected with underlying symmetries of the sets of solutions, and they show, assuming the Unique Games Conjecture, that for pairs of Boolean predicates, PCSPs that do not satisfy their conditions are NP-hard to solve with robust satisfaction algorithms. To do this, they must find hard instances of such problems. The authors provide a general recipe for constructing such instances, relating them in a novel and interesting way to the existence of certain configurations in the $n$-dimensional sphere.

These results do not fully characterize the PCSPs that have robust satisfaction algorithms, but finding such a characterization looks out of reach for the moment. However, the paper proves several interesting insights and results, introduces new proof techniques, and points to interesting questions and research directions.