Videos

On Approximability of Satisfiable Constraint Satisfaction Problems & Applications

Presenter
January 27, 2025
Abstract
The satisfiability problem for Constraint Satisfaction Problems (CSPs) asks whether an instance of a 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− greater than {0,1}, where P(x)=1 iff x is a satisfying assignment, the problem CSP(P) has every local constraint of the form the predicate P applied to the ordered set of k variables (or literals). One 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 ϵ 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 of finding α(P) for a given predicate P 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, relevant analytical theorems, and a proposed approximation algorithm. It will also present the applications of the analytical theorems to additive combinatorics, including improved bounds for sets free of restricted 3-term arithmetic progressions and 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.