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
Originating Calendar
Computer Science Speakers Calendar

       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