The Unique Games Conjecture and optimal approximation thresholds

The explanation

Here is a small puzzle. Three players, A, B and C, each pick a number 0, 1 or 2. B must pick the same as A. C must pick the same as B. A must pick C's number plus 1, counting round a clock of three, so 2 plus 1 is 0. Each rule has a special shape. Whatever one player picks, the rule allows exactly one reply from the other. A puzzle built only from such rules is called a unique game.

This one cannot be fully solved. Follow the rules round the triangle and A would have to equal A plus 1. But any two rules can be kept. Setting everyone to 0 keeps the first two. Trying all 27 choices confirms that two out of three is the best score. The score of a unique game is the largest share of rules any choice can keep.

In 2002, Subhash Khot conjectured that scores are hard to estimate. Take any two small error levels, such as 1 percent each. His Unique Games Conjecture says no fast method can always separate two kinds of puzzle. Some score at least 99 percent, others at most 1 percent. "Fast" here means a running time that grows like a fixed power of the puzzle's size. "No fast method" means none exists unless every problem in a large class called NP has one.

The conjecture matters because many other limits were proved from it. One is Max-Cut: split a network's points into two groups so that as many links as possible cross between them. A ring of five points allows at most four crossing links out of five. In 1995, Michel Goemans and David Williamson gave a fast method. On average it gets at least about 0.878567… of the best possible split. In 2007, Khot, Guy Kindler, Elchanan Mossel and Ryan O'Donnell showed that beating that ratio would break the conjecture. Without the conjecture, the proven barrier for Max-Cut stood at 16/17, about 0.941. The gap between 0.879 and 0.941 stayed open. Similar conditional limits followed. Khot and Oded Regev covered Vertex Cover in 2008. Prasad Raghavendra covered every problem of a broad type.

This paper proves the conjectureSource 1. It turns any logic puzzle of a standard kind into a unique game, quickly. Puzzles that can be solved become unique games scoring at least 99 percent. Puzzles that cannot become unique games scoring at most 1 percentSource 2. The same holds for any two error levels below one half, chosen in advanceSource 3.

The single difficulty was keeping the score near 100 percent when every answer allows only one replySource 4. The closest earlier work was finished by Khot, Dor Minzer and Muli Safra in 2018. It kept the score only near 50 percent. The paper shows why with one test. A player's answer is checked against a slightly jiggled version of the same question. Under the old jiggle, even an honest answer keeps its value only about half the timeSource 5. The paper builds a new jiggle from squared, nonlinear building blocks. Honest answers almost always survive it. Yet broad families of simple linear checks still notice it at least one time in eightSource 6. That keeps cheating answers from passing.

Read through the earlier work, the theorem now makes those conditional limits ordinary hardness resultsSource 7. Four companion papers also reach Max-Cut, Vertex Cover and two other problems by direct routes, without the conjecture. For Max-Cut, no fast method can beat 0.878567… unless every NP problem has a fast method. The results concern ordinary step-by-step methods, not methods that flip coinsSource 8. They also give no new algorithm for any of these problems.

How sure is this? A computer proof checker called Lean has checked formal versions of all five main statements. They are the unique games result and the four companion hardness results. Each is matched against a fixed reference statement by a tool called Comparator. The paper's other listed consequences are not in the Lean scope note. Specialists have begun to comment in public, but no independent review of the proofs has been published.

What it doesn't show. This does not give a fast algorithm for any of these problems.