«

Dana’s talk on OpenAI’s proof of the Unique Games Conjecture, now on YouTube!

Enjoy all three hours of this! Dana covers what the Unique Games problem is, the structure of a proof of its NP-hardness, exactly where the previous attempts to complete the proof (based on the Long Code and the Hadamard Code) got stuck, what new tree-based code the AI discovered, and how the new code gets around the Long Code and Hadamard Code’s limitations. She doesn’t get to the soundness analysis.

Feel free to ask questions in the comments. I might write some notes here later with my own doofus understanding of Dana’s talk. Experts are of course hard at work on more formal writeups of the proof (which will hopefully be more comprehensible than the AI’s writeup).

Email, RSS Follow

This entry was posted on Tuesday, November 10th, 2026 at 2:27 pm and is filed under AI, Announcements, Complexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.

Comment Policies:

After two decades of mostly-open comments, in July 2024 Shtetl-Optimized transitioned to the following policy:

All comments are treated, by default, as personal missives to me, Scott Aaronson---with no expectation either that they'll appear on the blog or that I'll reply to them.

At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I'll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I'll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet.

To the many who've asked me for this over the years, you're welcome!