Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science. The satisfiability problem for CSP asks whether an instance of CSP 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. For a given k-ary predicate P:[q]^k−>{0,1}, where P−1(1) denotes the set of satisfying assignments, the problem CSP(P) has every local constraints of the form the predicate P applied to the ordered set of k variables (or literals).
A most natural question is to ask for the precise threshold α(P) less than 1 for every NP-complete CSP(P) such that (i) there is a polynomial-time algorithm that finds an assignment satisfying α(P) fraction of the constraints on a satisfiable instance and (ii) for every \epsilon greater than 0, finding an (α(P)+ϵ) satisfying assignment is NP-hard. It is reasonable to hypothesize that such a threshold exists for every NP-complete CSP(P). This natural question 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 a work of Raghavendra that answers the question on almost-satisfiable instances. The talk will be based on a series of joint works with Subhash Khot and Dor Minzer.
