On this page
In 2002 a Princeton graduate student, Subhash Khot, published a short paper called On the power of unique 2-prover 1-round games. Its central guess became known as the unique games conjecture. The International Mathematical Union gave Khot the 2014 Rolf Nevanlinna Prize "for his prescient definition of the 'Unique Games' problem" and for leading the effort to understand its complexity.
Khot grew up in Ichalkaranji, Maharashtra, and Quanta Magazine reports that at 16 he achieved the highest score in the country in the IIT Joint Entrance Exam.
What is the unique games conjecture?
Picture a network of dots joined by lines. You must colour every dot from a fixed palette, and every line carries a rule. In a unique game the rules are strict in one way: once you choose the colour at one end of a line, the colour at the other end is fixed.
Khot cared about networks where the best colouring meets most rules but not all, say 99%. Intuition says a colouring that meets only 1% should then be easy to find. As Quanta explains, the conjecture says this intuition is wrong. Formally, it says that telling an almost fully satisfiable instance apart from one where almost nothing can be satisfied is NP-hard.
Why is a perfect answer easy but a near-perfect one hard?
Try the puzzle in the picture above. It has six dots, three colours (0, 1 and 2) and nine arrows. An arrow marked +1 means "the colour at the head is the colour at the tail plus one", wrapping round so that 2 + 1 = 0.
Give the top-left dot colour 0.
Follow the arrows. Each one forces the next dot's colour, with no guessing.
Check every rule. If one breaks, try starting with 1, then 2.
So when every rule can be met, following the arrows finds the answer quickly. Now trace a loop. Top-middle to top-right adds 1, then top-right to bottom-right adds 2, so bottom-right must match top-middle. But the dashed arrow says bottom-right is top-middle plus one. These rules clash, so at most 8 of the 9 can hold, and the colouring shown reaches exactly 8.
With millions of dots and small clashes scattered everywhere, following arrows breaks down. The conjecture says that, unless P = NP, no fast method can reliably tell a 99% network from a 1% one.
Why did it win the Nevanlinna Prize?
Its power lies in what follows. Take Max-Cut: split a network's dots into two groups so that as many lines as possible run between them. In 1995 Michel Goemans and David Williamson gave a fast method for it. In 2007 Khot, Guy Kindler, Elchanan Mossel and Ryan O'Donnell showed in the SIAM Journal on Computing that if the unique games conjecture holds, beating the Goemans-Williamson ratio of about 0.878567 is NP-hard. The 1995 method would be the best possible.
In 2008 Prasad Raghavendra went further, Quanta reports: if the conjecture is true, one classic algorithm is the best strategy for every constraint problem with no perfect solution.
Andrew Appel, then chair of computer science at Princeton, summed it up in the department's prize announcement: "We knew for 40 years that some problems are hard to solve exactly. Khot shows how many more problems are hard to get even an approximate answer for."
For the background, read our pieces on Stephen Cook and NP-completeness and Madhu Sudan and the PCP theorem.
Has the unique games conjecture been proved?
Not in a form experts had confirmed when Quanta reported on it on 7 October 2026. Quanta says that in 2018 Dor Minzer, then a graduate student, played a leading role in the first significant advance, a 2-to-2 games result with Khot and Muli Safra. In September 2026 Minzer and his graduate students Yumou Fei and Shuo Wang posted a 95-page paper proving a slightly weaker 4-to-1 version of Khot's related 2-to-1 conjecture.
On 6 October 2026 OpenAI announced a proof of the unique games conjecture itself. Quanta notes that the release's AI-generated manuscript containing a proof of the 2-to-1 conjecture had no human editing or review by independent experts. Before the announcement, Mark Braverman of Princeton told Quanta that an AI proof could still open new directions for researchers: "It's not 'one and done.'"
What can a student learn from Khot?
Khot told Quanta in 2014: "I'm perfectly happy to spend very long periods on a single problem." His question also suggests habits for JEE practice:
When a problem resists you, ask what a rough answer looks like: a bound, a limiting case or an estimate.
When conditions seem to clash, trace the loop where they contradict, as in the puzzle above.
Keep one hard problem open for days rather than jumping to the solution.
If graphs or modular arithmetic are new to you, the Fermi Concept Library gives each concept in mathematics and computing its own lesson. Fermi's AI tutor can work through a puzzle like this one with you, deciding whether to explain, ask or show, so you find the clash yourself.
