MIT trio rush out major graph-coloring proof ahead of OpenAI's Unique Games proof
Dor Minzer and two students proved a 4-to-1 version of Khot's conjecture. It settles a decades-old coloring question just weeks before OpenAI's announcement.
Why it matters · This is a real advance on the limits of approximate problem-solving. It is also an early case of human researchers changing how they publish because AI could get there first.
On September 11, 2026, rumors spread that OpenAI had proved the unique games conjecture, one of the best-known open problems in computational complexity. MIT's Dor Minzer and his graduate students Yumou Fei and Shuo Wang were still writing up a related result. Three days later they posted a 95-page paper with a warning on the first page: it is "complete mathematically, but it is not in the shape we wished to share in." On October 6, OpenAI announced its proof along with 376 other results.
What the conjectures say
Both problems are about satisfying many constraints that pull against each other. In Subhash Khot's 2002 version, you color the nodes of a graph, and each edge has a rule: once one endpoint has a color, the other endpoint's color is fixed. The conjecture says that when the best coloring satisfies 99% of the rules, it can still be hard to find one that satisfies even a tiny fraction. Prasad Raghavendra showed in 2008 that if this is true, one classic algorithm is the best possible for every constraint problem with no perfect solution.
The conjecture has a gap, though. It says nothing about cases where all the constraints can be satisfied. To cover those, Khot proposed the 2-to-1 games variant, where each rule allows two colors on the other side. The claim is that finding even a weak approximation stays hard even when a perfect solution exists.
What the MIT team proved
Minzer, Fei and Wang proved a slightly weaker 4-to-1 version, which has almost the same consequences. Their strategy was to build a mathematical bridge from the coloring problem to one whose difficulty is already understood. Like Minzer's 2018 milestone, it goes through . Fei and Wang found a new way to construct those codes in 2025. Fitting it into the rest of the proof took repeated failures, until it worked in April 2026. "We took five failures and managed to staple this [new code] on top of them," Minzer said.








