- This event has passed.
CSE Colloquium: Amey Bhangale
April 29, 2019 @ 11:00 am - 12:00 pm UTC-5
Speaker: Amey Bhangale
Date: Monday, April 29
Time: 11-12pm
Location: HBL 1947 Room
Title: Unique Games with value half and its applications.
Abstract: PCP Theorem characterizes the class NP and gives hardness of approximation for many optimization problems. Despite this, several tight hardness of approximation results remain elusive via the PCP theorem. In 2002, Khot proposed the Unique Games Conjecture. Since the formulation of the conjecture, it has found interesting connections to the tight hardness of approximation results for many optimization problems.
In this talk, I will discuss recent developments about the Unique Games Conjecture. The 2-to-2 Games Theorem implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least 1/2 fraction of the constraints vs. no assignment satisfying 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 guarantee to convert the known Unique Games-hardness results to NP-hardness for several optimization problems.
Based on joint work with Subhash Khot.
