BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/546
DTSTAMP:20230914T125929Z
SUMMARY:On Khot's Unique Contribution
DESCRIPTION:Speaker: Prahladh  Harsha\n\nAbstract: \nIn 2002\, Subhash Khot
  proposed the "Unique Games Conjecture" a conjecture about the computation
 al hardness of a specific optimization problem. Since then\, a remarkable 
 body of work has gone into showing how this conjecture provides a single p
 oint explanation for the phase transition between easiness and hardness of
  approximating several other optimization problems. Today\, as a result of
  this work\, we have a better understanding of the effectiveness of semi-d
 efinite programming convex relaxations. This\, despite the lack of consens
 us among the community about the veracity of the conjecture\; there have b
 een attempts to both prove and disprove the conjecture. Furthermore\, this
  work led to a better understanding of the limits of metric embeddings\, t
 iling in high dimensional space etc\, results which are true irrespective 
 of the truth of the conjecture. In this talk\, I'll survey this remarkable
  body of work describing the context and statement of the conjecture (no p
 rior knowledge will be assumed).\n \n[Khot won the Nevanlinna Prize at IC
 M 2014 for his work related to the Unique Games Conjecture]\n
URL:https://www.tcs.tifr.res.in/web/events/546
DTSTART;TZID=Asia/Kolkata:20141029T160000
DTEND;TZID=Asia/Kolkata:20141029T170000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR