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).

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town