In 2002, Subhash Khot proposed the "Unique Games Conjecture" a conjecture about the computational hardness of a specific optimization problem. Since then, a remarkable body of work has gone into showing how this conjecture provides a single point 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-definite programming convex relaxations. This, despite the lack of consensus among the community about the veracity of the conjecture; there have been attempts to both prove and disprove the conjecture. Furthermore, this work led to a better understanding of the limits of metric embeddings, tiling 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 prior knowledge will be assumed).
[Khot won the Nevanlinna Prize at ICM 2014 for his work related to the Unique Games Conjecture]
