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.
