Science & Space · Mathematics & Computer Science

The Unique Games Conjecture

A simple explanation of computer science's big question about "good enough" answers, and the October 2026 AI proof that it is true

Some problems are easy to check but seem impossible to solve quickly. A sudoku is the everyday example: checking a filled-in grid takes a minute, while finding the answer can take much longer. For thousands of real problems (scheduling, routing, splitting networks, packing), computer scientists believe there is no fast way to find the perfect answer. So the practical question becomes: how close to perfect can a fast algorithm get? The Unique Games Conjecture is a bold claim that answers that question for a huge number of problems at once.

The Problem in Plain Language

Step 1: easy to check, hard to solve

Moitra starts with satisfiability, or SAT (transcript, around 2:05:26). You have a list of yes/no switches and a list of rules like "switch 1 is on, or switch 3 is off, or switch 7 is on." Can you set the switches so every rule is satisfied? If someone hands you an answer, checking it is quick. Finding one yourself appears to be very hard. Whether that gap is real is the P versus NP problem, and Moitra notes that a lot of cryptography and e-commerce rests on the assumption that it is.

Step 2: even "almost" is hard (the PCP theorem)

In the 1990s, computer scientists proved the PCP theorem, which Moitra says was big enough to make the front page of The New York Times (around 2:07:06). It says, roughly, that you can rewrite any of these puzzles so that a cheater gets caught by spot-checking just a few random rules. The surprising consequence is about approximation: for many problems, it is not only hard to find a perfect answer, it is even hard to tell the difference between a puzzle where 100% of the rules can be satisfied and one where at most 99% can.

Step 3: the unique games version

A "unique game" is a special kind of puzzle. You give every item in a network a label (think of a color or a dial setting), and each connection between two items comes with a rule. The rules are unique: once you pick one item's label, the rule forces exactly one label for its neighbor. That makes the puzzle trivially easy if every rule can be satisfied, because you just pick a starting label and follow the chain.

The Unique Games Conjecture says that if almost every rule can be satisfied (say 99%), it is still hard for any fast algorithm to find a labeling that satisfies even a small fraction (say 1%). Moitra describes it as a strengthening of the PCP theorem for a certain type of "label cover" problem (around 2:09:19).

Why It Matters

• It settles "how good is good enough" for many problems at once. According to Moitra, if the conjecture holds, then "for a huge swath of problems, we would actually know what is the best approximation algorithm, and it would be something very simple" (02:10:10).
• It explains why certain simple algorithms seem unbeatable. Moitra points to Prasad Raghavendra's work, which shows that if the conjecture is true, a single kind of algorithm gives the optimal result for a whole family of constraint problems (around 02:12:19). Classic examples studied under the conjecture include Max-Cut and Vertex Cover.
• It was genuinely contested. Moitra recalls the 2010s as a back-and-forth where new results kept changing whether people believed it. He quotes a quip he heard: "maybe God's gonna decide whether it's true or false based on which side is working harder" (02:10:50). He says he sometimes sided with the doubters, because the conclusion "just looked to me too strong to be true" (02:12:19).

The October 2026 Breakthrough

According to Moitra, "one of the headlining results in the OpenAI drop of proofs was that the Unique Games Conjecture is true" (02:10:50). He stressed that it built on serious human progress. Dor Minzer and Irit Dinur, among others, proved a weaker version called the Two-to-One Games Theorem, which he called "a shot heard round the world in theoretical computer science" because it finally gave a viable path toward unique games (02:11:32). Before the AI result, he says, it sounded like humans might get there "with another 10, 20 years."

What the guests said

• It was rumored. Moitra says rumors had circulated for weeks, and that Minzer even posted a paper with a footnote saying he was releasing his approach sooner because of the rumors (02:12:49).
• The papers are hard to read. In Moitra's words, "they're not very readable papers. It's not like you can point to them and really quickly identify what's a new key idea" (02:12:49).
• Khot's reaction. Hours before the drop, Moitra asked Subhash Khot whether he would read a positive proof if one came out. Khot said "No" (02:14:08).
• The human cost. Moitra worries that field-defining problems were resolved in one night and that people may lose enthusiasm for the paths they were exploring. His advice to young mathematicians: be more curious than you are smart (around 2:15:35 to 2:18:46).

Outside the episode

OpenAI's preprint, The Unique Games Theorem (dated September 23, 2026), claims an explicit reduction from 3SAT that resolves the conjecture "positively in its usual edge-value formulation." The release is described on OpenAI's announcement page. Expert review is still ongoing.

Resources

• Lex Fridman Podcast #503: AI Crisis in Math (Moitra, Brunton, Kontorovich)
• Episode #503 transcript (complexity theory chapter starts 2:04:39)
• Episode #503 on YouTube
• Wikipedia: Unique games conjecture
• Subhash Khot (2002): On the power of unique 2-prover 1-round games
• Dinur, Khot, Kindler, Minzer, Safra: Towards a proof of the 2-to-1 games conjecture?
• Quanta Magazine: First Big Steps Toward Proving the Unique Games Conjecture (2018)
• OpenAI: Sharing AI progress in mathematics (Oct 6, 2026)
• OpenAI preprint: The Unique Games Theorem (PDF)