On Approximability of Satisfiable CSPs & Applications
Amey Bhangale (UC Riverside)
Monday, May 11 2026, 2-3pm
Abstract:
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. By the Dichotomy Theorem of Bulatov and Zhuk, this problem is either in P or NP-complete.
A natural question 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 Hastad), 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.
A natural question 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 Hastad), 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.