AI Proof Rumors Spur Researchers to Publish a Milestone on Unique Games

Summary

Rumors that OpenAI had solved the Unique Games Conjecture pushed MIT professor Dor Minzer and his graduate students Yumou Fei and Shuo Wang to publish a 95-page paper three days after the messages began circulating. Their work, developed over seven years and posted in September 2026, proves a slightly weaker 4-to-1 games version of a conjecture proposed by Subhash Khot, rather than the original 2-to-1 version. The result still has important consequences: it implies that even when a graph is known to be three-colorable, finding a valid coloring can remain difficult regardless of how many additional colors are allowed. The team reached the proof after repeated failures and by combining an unusual error-correcting-code construction with earlier components of their approach. They acknowledged that the rushed manuscript was mathematically complete but poorly written, with later sections lacking connecting prose. On October 6, OpenAI announced a Lean-verified proof of the original Unique Games Conjecture and 376 other mathematical results, including an AI-generated 2-to-1 conjecture proof that had not received human editing or independent expert review. Researchers viewed OpenAI’s release with both interest and concern, noting that AI proofs may expose new research directions but can make it difficult to identify the assumptions and ideas driving a result. Minzer also warned that AI could remove the educational value of failure and make researchers less willing to pursue long projects if they fear being overtaken by a large company.