Computer Science Speakers Calendar

View Full Calendar

On Approximability of Satisfiable CSPs

Event Type
Computer Science
Thomas M. Siebel Center for Computer Science 201 North Goodwin Avenue, Urbana, IL 61801, Room# 3102
Apr 5, 2024   3:00 pm  
Amey Bhangale (UC Riverside)
Michael A Forbes

       Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science. The satisfiability problem for CSP asks whether an instance of 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−1(1) denotes the set of satisfying assignments, 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 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, a relevant analytic hypothesis and some progress on it, and Raghavendra's work that answers the question in almost-satisfiable instances.


       The talk will be based on a series of joint works with Subhash Khot and Dor Minzer.

link for robots only