On Approximability of CSPs on Satisfiable Instances

Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science, 3SAT being a prominent example.

Let Σ be an alphabet and P:Σk→{0,1} be a fixed predicate. The assignments in P−1(1) are deemed as satisfying assignments to the predicate.  The k-ary CSP corresponding to the predicate, denoted CSP(P), consists of n variables x1,...,xn taking values over Σ and m constraints C1,...,Cm where each constraint Cj is the predicate P applied to an ordered subset of k variables.  Sometimes variables are allowed to be in negated form (in case of Boolean alphabet) or a mix of predicates derived from the same template predicate P is allowed. 

The satisfiability problem for CSP(P) asks whether an instance of CSP(P) has a (fully) satisfying assignment, i.e. an assignment that satisfies all constraints.  This problem is known to be in class P or is NP-complete by the recently proved Dichotomy Theorem of Bulatov and Zhuk. An example of a CSP that is in class P is 3LIN, where constraints are linear equations over an Abelian group, each equation having three variables.

A most natural question is to ask for the precise threshold α(P)<1 for every NP-complete CSP(P) such that (i) there is an efficient algorithm that finds an assignment satisfying α(P) fraction of the constraints on a satisfiable instance and (ii) for every ϵ>0, finding α(P)+ϵ satisfying assignment is hard. It is reasonable to hypothesize that such a threshold exists.

This natural question, surprisingly, is wide open, though such thresholds are known for some specific predicates (e.g., 7/8 for 3SAT by Hastad). The talk will present recent work initiating a systematic study of this question, a relevant analytic hypothesis and some progress on it, and connections to the Dichotomy Theorem and a work of Raghavendra that answers the question on *almost-satisfiable* instances.

Joint work with Amey Bhangale and Dor Minzer.