BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1384
DTSTAMP:20240116T043225Z
SUMMARY:On Approximability of Satisfiable CSPs
DESCRIPTION:Speaker: Prof. Amey Bhangale (University of California\, Rivers
 ide)\n\nAbstract: \nConstraint 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 know
 n to be in class P or is NP-complete by the recently proved Dichotomy Theo
 rem of Bulatov and Zhuk. For a given k-ary predicate P:[q]^k−>{0\,1}\, w
 here P−1(1) denotes the set of satisfying assignments\, the problem CSP(
 P) has every local constraints of the form the predicate P applied to the 
 ordered set of k variables (or literals).\nA most natural question is to a
 sk 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 assignm
 ent satisfying α(P) fraction of the constraints on a satisfiable instance
  and (ii) for every \\epsilon greater than 0\, finding an (α(P)+ϵ) satis
 fying assignment is NP-hard. It is reasonable to hypothesize that such a t
 hreshold exists for every NP-complete CSP(P). This natural question is wid
 e open\, though such thresholds are known for some specific predicates (e.
 g.\, 7/8 for 3SAT by Hastad). \nThe talk will present recent work initiat
 ing a systematic study of this question\, a relevant analytic hypothesis a
 nd some progress on it\, and a work of Raghavendra that answers the questi
 on on almost-satisfiable instances. The talk will be based on a series of 
 joint works with Subhash Khot and Dor Minzer.\n
URL:https://www.tcs.tifr.res.in/web/events/1384
DTSTART;TZID=Asia/Kolkata:20240116T160000
DTEND;TZID=Asia/Kolkata:20240116T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR