BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1054
DTSTAMP:20230914T125948Z
SUMMARY:Unique Games with Value Half and its Applications.
DESCRIPTION:Speaker: Amey Bhangale (University of California\, Riverside\nC
 alifornia\, U.S.)\n\nAbstract: \nAbstract: PCP Theorem characterizes the c
 lass NP and gives hardness of approximation for many optimization problems
 . Despite this\, several tight hardness of approximation results remain el
 usive via the PCP theorem. In 2002\, Khot proposed the Unique Games Conjec
 ture. Since the formulation of the conjecture\, it has found interesting c
 onnections to the tight hardness of approximation results for many optimiz
 ation problems. \n\nIn this talk\, I will discuss recent developments abou
 t the Unique Games Conjecture. The 2-to-2 Games Theorem implies that it is
  NP-hard to distinguish between Unique Games instances with assignment sat
 isfying at least 1/2 fraction of the constraints vs. no assignment satisfy
 ing more than \\eps fraction of the constraints\, for every constant \\eps
 >0. We show that the reduction can be transformed in a non-trivial way to 
 give a stronger guarantee on the Unique Games instance and use this guaran
 tee to convert the known Unique Games-hardness results to NP-hardness for 
 several optimization problems. \n\nBased on joint work with SubhashK Khot.
 \n
URL:https://www.tcs.tifr.res.in/web/events/1054
DTSTART;TZID=Asia/Kolkata:20200218T141500
DTEND;TZID=Asia/Kolkata:20200218T151500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR