On Approximability of Satisfiable CSPs & Applications

Amey Bhangale ( CSE Department at University of California, Riverside )

The satisfiability problem for Constraint Satisfaction Problems (CSPs) asks whether a CSP instance admits an assignment that satisfies all constraints. For a k-ary predicate P:[q]^k -> {0,1}, where P(x)=1 iff x satisfies the constraint, the problem CSP(P) consists of constraints obtained by applying P to ordered k-tuples of variables. In a recent breakthrough, the Dichotomy Theorem of Bulatov and Zhuk shows that this problem is either in P or NP-complete.

A natural question now is to determine the threshold \alpha(P) < 1 for each NP-complete CSP(P) such that (i) there is a polynomial-time algorithm that finds an assignment satisfying an \alpha(P) fraction of constraints on satisfiable instances, and (ii) for every \epsilon>0, finding an assignment satisfying an (\alpha(P)+\epsilon) fraction is NP-hard.

While such thresholds are known for some predicates (e.g., 7/8 for 3SAT by H{\aa}stad), determining \alpha(P) in general remains widely open.

This talk presents recent work initiating a systematic study of this question, including new analytical theorems and a proposed approximation algorithm. I will also discuss applications to additive combinatorics, including improved bounds for sets avoiding restricted 3-term arithmetic progressions and results related to the density Hales--Jewett theorem in [3]^n.

The talk will be based on joint works with Subhash Khot, Yang P. Liu, and Dor Minzer.