Subhash Khot: On Approximability of CSPs on Satisfiable Instances

Tuesday, November 30, 2021 - 4:00pm to 5:00pm

Location:

Email jmtaft@mit.edu for link

Speaker:

Subhash Khot, New York University

Seminar group:

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

Let $\Sigma$ be an alphabet and $P:\Sigma^k \rightarrow \{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 $x_1,...,x_n$ taking values over $\Sigma$ and $m$ constraints $C_1,...,C_m$ where eachconstraint $C_j$ is the predicate $P$ applied to an ordered subset of $k$ variables.

Sometimes variablesare allowed to be in negated form (in case of Boolean alphabet) or a mixof predicatesderived 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 $\alpha(P) < 1$ for every NP-complete $CSP(P)$ such that (i) there is an efficient algorithm that finds an assignment satisfying $\alpha(P)$ fraction of the constraints on a satisfiable instance and (ii) for every $\epsilon > 0$, finding $\alpha(P)+\epsilon$ 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.