Date: August 31, 2026
Title: CSPs and Inverse Theorems for 3-wise Correlations of Functions
Speaker: Amey Bjangale, Assistant Professor, UC Riverside
Abstract: Constraint satisfaction problems (CSPs) provide a rich source of algebraic and analytic questions at the interface of combinatorics, optimization, and computational complexity. A landmark theorem of Bulatov and Zhuk classifies the complexity of every finite constraint satisfaction problem, showing that each is either solvable in polynomial time or NP-complete.
This dichotomy raises a natural quantitative question: for an NP-complete problem, what is the optimal approximation threshold? Raghavendra’s celebrated result gives a general characterization of the optimal approximation ratio when the input instance is promised to be almost satisfiable. In contrast, much less is known when the instance is promised to be fully satisfiable. More precisely, for each constraint predicate P, one seeks the largest constant \alpha(P) for which there is a polynomial-time algorithm that, on every satisfiable instance, finds an assignment satisfying at least an \alpha(P) fraction of the constraints, while achieving (\alpha(P)+\epsilon) for any \epsilon>0 is NP-hard. Beyond a few examples, such as Håstad's celebrated 7/8 threshold for Max 3SAT, little is known about these optimal constants.
I will present our work on a systematic study of these approximation thresholds. The main ingredients are new inverse theorems for 3-wise correlations of functions. I will also discuss applications of these inverse theorems to problems in additive combinatorics.
This talk will be based on joint works with Subhash Khot, Yang P. Liu, and Dor Minzer.
Bio: Amey Bhangale is an Associate Professor of Computer Science and Engineering at the University of California, Riverside. His research focuses on approximation algorithms, hardness of approximation, constraint satisfaction problems, probabilistically checkable proofs, and Boolean function analysis. He earned his undergraduate degree from VJTI Mumbai and his Ph.D. from Rutgers University in 2017 under Swastik Kopparty. Before joining UCR, he held research positions at the Weizmann Institute of Science and the Simons Institute for the Theory of Computing. He received the UC Hellman Fellowship in 2023 and received an NSF CAREER Award in 2025 for his research.