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 and why people cared about it, 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, the new tree-based code that 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 som...
Read full article →