Many important computational problems involve optimization: finding the best schedule, the shortest route, or the most efficient allocation of resources.
A foundational achievement of theoretical computer science—the Probabilistically Checkable Proofs (PCP) Theorem of the early 1990s—showed that for a broad class of such problems, not only is finding an exact solution computationally infeasible (known as NP-hard), but even finding a good approximate solution can be difficult to prove.
In 2002, Subhash Khot, Member (2003–04) in the School of Mathematics, proposed the Unique Games Conjecture (UGC), which, if true, shows that, for a vast family of optimization problems, the best-known algorithms are already optimal and good approximate solutions can be considered NP-hard. The conjecture became one of the most important and hotly debated open questions in the field.
This April, Khot and Irit Dveer Dinur, Betsey Lombard Overdeck Theory of Computing Professor, alongside their School of Mathematics collaborators Dor Minzer, Member (2018–20); Shmuel Avraham Safra, Member (2004–05); and Guy Kindler, Member (2004–05), won the National Academy of Sciences’s Michael and Sheila Held Prize for work which represents the most significant advance toward resolving Khot's conjecture.
In a series of papers culminating in 2018, the recipients proved the 2-to-2 Games Theorem, a closely related variant of the UGC. Beyond providing strong evidence that the full conjecture is true, the theorem has direct consequences for fundamental problems including vertex cover and graph coloring.
