The Unique Games Conjecture – Proved (!!?)

Abstract: The Unique Games Conjecture of Khot says that it is NP-hard, given a system of linear equations of the form xi-xj=bij (mod p) over variables x1…xn, where 99% fraction of the equations can be satisfied, to find an assignment satisfying 1% of the equations (here p is a sufficiently large constant).

This conjecture implies optimal inapproximability results for many optimization problems. 

A few weeks ago OpenAI released a writeup with a proof of the Unique Games Conjecture, as well as a Lean formalization of the proof. The writeup, like others released that day, is not written in a way that’s especially readable to human mathematicians. 

My goal in this talk is to offer my mental map of the proof, in a way that’s helpful to theoretical computer scientists who are familiar with the area. I think of the innovation as a new code construction, “Hadamard with a noise test.” I’ll sketch how it fits into the NP-hardness reduction. Then I’ll describe the code construction fully and sketch its soundness analysis.    

I’ll also point out a couple of ingredients of the proof that are of independent interest, like a simple quadratic that behaves “like a linear,” and a probability bound using a trick with harmonic numbers.

Speaker Bio: Dana Moshkovitz is a professor of Computer Science at UT Austin. Her research is in Theoretical Computer Science. Much of it focuses on the limitations of approximation algorithms and probabilistic checking of proofs. Dana did her PhD at the Weizmann Institute in Israel. Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in 2009, and part of this work was awarded the FOCS 2008 Best paper. Dana went on to spend a couple of years at Princeton University and the Institute of Advanced Study before joining MIT as an assistant professor. Dana is the recipient of the Jerome Saltzer teaching award of MIT EECS.