Did AI Prove the Unique Games Conjecture?
Ankur Moitra says a headlining result in the OpenAI drop is that the unique games conjecture is true. He had been on the side of the doubters, because the conjecture sounded too nice to be true.
Unique games strengthens the PCP theorem from the 1990s, a result that made the front page of the New York Times. A verifier can catch a false proof by inspecting only a constant number of random spots. If unique games holds, a huge set of problems has a best approximation algorithm, and that algorithm is simple.
Dor Minzer and Irit Dinur proved a weaker two-to-one games theorem that looked like a path humans might finish in another 10 or 20 years. The OpenAI release showed the full conjecture is true.
#503 – AI Crisis in Math: Navier-Stokes, Riemann Hypothesis & Complexity Theory ·
From the transcript
Sounds good. Very cool. Ankur, one of my favorite topics is theoretical computer science. You're one of the world experts in many of its problems. So I'd love to ask you about one of the big problems that's been solved in this OpenAI drop, which is the unique games conjecture. Can you give people an intuition about what this problem is, why it's a big deal, and what are some aspects of the proof that are interesting? Yes, I'd love to.
So let me give you a little bit of a background. So let's start off with complexity theory 101. So one of the most important problems in theoretical computer science is the satisfiability problem. So the thing to keep in your mind is imagine you've got variables X1 to Xn, and they can take on either true or false values. And what I'm going to do is I'm going to create a big formula out of them.