As AI Closed In on ‘Unique Games’ Proof, Researchers Raced to Beat the Machines

On September 11, 2026, Dor Minzer, a computer scientist at MIT, received messages suggesting that OpenAI had allegedly proven the unique games conjecture, a major unsolved problem in theoretical computer science. The conjecture deals with the difficulty of satisfying multiple constraints in problems like graph coloring, where nodes must be assigned colors based on specific edge rules. Minzer initially dismissed the rumors as a joke, but they gained credibility as more messages arrived. The unique games conjecture states that even if a problem's best solution satisfies 99% of constraints, finding even a very poor approximation (e.g., satisfying 1% or 0.001% of constraints) remains computationally hard. A proof of this conjecture would imply that many other problems cannot be solved more efficiently than current methods allow. OpenAI’s rumored breakthrough threatened to overshadow Minzer’s ongoing work.

Minzer and his graduate students, Yumou Fei and Shuo Wang, had recently proven a related result but had not yet finalized their 95-page paper. Fearing being scooped by OpenAI’s potential announcement, they rushed to publish their draft on September 14, 2026, despite it being mathematically complete but poorly formatted. Their paper addressed a variant of the 2-to-1 games problem, a looser version of the unique games conjecture where constraints allow two possible color options per edge instead of one. While not a direct proof of the original conjecture, their result implied significant consequences, including the difficulty of graph-coloring problems even with unlimited colors. The paper included a disclaimer noting its lack of clarity in later sections due to the rushed timeline.

Minzer’s work on the 2-to-1 games problem spanned seven years, beginning with his graduate student contributions in 2018 to a celebrated advance toward proving Khot’s conjectures. Progress stalled until 2025, when Fei and Wang, in their first year of graduate school, joined Minzer to tackle the problem. Their breakthrough came in April 2026 after months of failed attempts, which they described as trying to fit mismatched puzzle pieces together. The trio succeeded by integrating a new approach to error-correcting codes—methods for detecting and fixing errors in transmitted messages—into their proof framework. Their final result proved a slightly weaker 4-to-1 version of the 2-to-1 conjecture, where constraints allow four color options instead of two.

The unique games conjecture, proposed by Subhash Khot in 2002, is a foundational question in computational complexity theory, which studies the inherent difficulty of mathematical problems. It focuses on constraint satisfaction problems, where multiple rules (constraints) must be satisfied simultaneously. For example, in a graph-coloring problem, nodes represent variables, and edges represent constraints on their relationships. The conjecture asserts that even when the best solution satisfies most constraints (e.g., 99%), finding a solution that satisfies a tiny fraction (e.g., 1%) remains computationally intractable. This claim has broad implications, linking to problems in geometry, voting systems, and algorithm design. Khot also proposed a variant called the 2-to-1 games problem, where constraints allow two possible color options per edge.

On October 6, 2026, OpenAI announced a proof of the unique games conjecture alongside 376 other mathematical results, all generated by artificial intelligence. Their proof was presented in a Lean-verified manuscript, a format where proofs are checked by automated software to ensure correctness. Unlike Minzer’s human-written and manually verified work, OpenAI’s proof did not undergo human review or editing by independent experts. Researchers reacted with a mix of curiosity and concern. While some saw potential in AI-generated proofs to uncover new research directions, others criticized the lack of transparency and peer review. Mark Braverman of Princeton University noted that math by press release could undermine the collaborative and rigorous nature of mathematical research.