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.
Short Bio : Amey Bhangale is currently an Assistant Professor in the CSE Department at the University of California, Riverside. He completed his PhD at the Rutgers University in 2017 under the supervision of Swastik Kopparty. He subsequently held postdoctoral positions at the Weizmann Institute of Science (hosted by Irit Dinur) and was a research fellow at the Simons Institute for the Theory of Computing. His research interests include approximation algorithms, probabilistically checkable proofs, hardness of approximation, and analysis of Boolean functions.
