On Approximability of Satisfiable CSPs
- Event Type
- Seminar/Symposium
- Sponsor
- Computer Science
- Location
- Thomas M. Siebel Center for Computer Science 201 North Goodwin Avenue, Urbana, IL 61801, Room# 3102
- Date
- Apr 5, 2024 3:00 pm
- Speaker
- Amey Bhangale (UC Riverside)
- Contact
- Michael A Forbes
- miforbes@illinois.edu
- Phone
- 217-300-0454
- Views
- 154
- Originating Calendar
- Siebel School 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.