[Colloquium] CS Theory Seminar - Tuesday, November 18 (Kent)

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Amey Bhangale
Assistant Professor, University of CA, Riverside

[image.png]

Tuesday, November 18, 2025, at 3:30pm
Kent Chemical Laboratory, Room 102



Title: On Approximability of Satisfiable Constraint Satisfaction Problems & Applications

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−>{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.



Bio: Amey Bhangale is an Assistant Professor in the Computer Science Department at the University of California, Riverside. He finished his Ph.D. at Rutgers University under the guidance of Swastik Kopparty. Before joining UC Riverside, he was a postdoctoral fellow at the Weizmann Institute of Science, hosted by Irit Dinur. He is interested in approximation algorithms, hardness of approximation, and the analysis of Boolean functions. His research is supported by the Hellman fellowship award and the NSF CAREER award.



  Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251112/ff4c034c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 232670 bytes
Desc: image.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251112/ff4c034c/attachment-0001.png>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251112/ff4c034c/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251112/ff4c034c/attachment-0003.txt>