On Approximability of Satisfiable Constraint Satisfaction Problems and Applications

Explore a computer science seminar that delves into the approximability of Satisfiable Constraint Satisfaction Problems (CSPs) and their applications. Learn about the fundamental threshold α(P) for NP-complete CSPs and discover how this threshold determines the boundary between polynomial-time solvable instances and NP-hard problems. Examine recent analytical theorems and a proposed approximation algorithm that contribute to the systematic study of this open question. Gain insights into practical applications in additive combinatorics, including improved bounds for sets free of restricted 3-term arithmetic progressions and the density Hales-Jewett theorem in [3]^n. Understand the implications of joint research conducted with Subhash Khot, Yang P. Liu, and Dor Minzer, presented by UC Riverside's Amey Bhangale at the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar.