Talk by Dana Moshkovitz: The Unique Games Conjecture – Proved (!!?)
In my “Mathocalypse” post, I mentioned that my wife Dana—who’s been working on Subhash Khot’s Unique Games Conjecture since ~2009, for the entire time I’ve known her—has for the past few weeks (while on sabbatical at the Simons Institute in Berkeley) been spending essentially all of her time laboring to understand OpenAI’s recent proof of the conjecture. Having now studied the proof closely in collaboration with Subhash Khot himself, Johan Håstad, Dor Minzer, and other colleagues, and (naturally) GPT-6 Astra, Dana probably now understands this crown jewel of OpenAI’s release as well as anyone does. This week, she gave two well-received whiteboard talks on the proof at Simons Institute. So, I and others encouraged her to give the same talks next week at UT Austin when she’s back here, and Dana agreed! Because of the large timely interest, we’re going to do a live Zoom option, and will also record the talk for later sharing on YouTube. Please note: While all are welcome, this is a 2-hour technical talk. The first hour will review key ideas from hardness of approximation, while the second hour will describe the new construction. —SA
Title: The Unique Games Conjecture – Proved (!!?)
Speaker: Dana Moshkovitz (UT Austin)
When: Wednesday Nov. 4, 3:30-5:30pm US Central (with a brief break in the middle)
Where: UT Austin, Gates Dell Complex 6.302. Live Zoom will be available here, and a recording will be available later.
Abstract: The Unique Games Conjecture of Khot says that it is NP-hard, given a system of linear equations of the form xi-xj=bij (mod p) over variables x1…xn, where 99% fraction of the equations can be satisfied, to find an assignment satisfying 1% of the equations (here p is a sufficiently large constant).
This conjecture implies optimal inapproximability results for many optimization problems.
A few weeks ago OpenAI released a writeup with a proof of the Unique Games Conjecture, as well as a Lean formalization of the proof. The writeup, like others released that day, is not written in a way that’s especially readable to human mathematicians.
My goal in this talk is to offer my mental map of the proof, in a way that’s helpful to theoretical computer scientists who are familiar with the area. I think of the innovation as a new code construction, “Hadamard with a noise test.” I’ll sketch how it fits into the NP-hardness reduction. Then I’ll describe the code construction fully and sketch its soundness analysis.
I’ll also point out a couple of ingredients of the proof that are of independent interest, like a simple quadratic that behaves “like a linear,” and a probability bound using a trick with harmonic numbers.
Follow
Comment #1 October 30th, 2026 at 8:30 pm
Scott,
Can you give a number 1-10 for how novel she takes the techniques used in the proof to be? Is it a clever combination of old ideas etc
Comment #2 October 30th, 2026 at 8:35 pm
Fan of the Blog #1: I’ll let her give a number if she wants. 🙂
But she’s described the proof to me as consisting of a totally alien new error-correcting code — unlike any that human PCP experts had proposed — plus a lot of standard, well-understood techniques to lift that code to a PCP and hence a proof of the UGC (with the latter, more “boring” part being the part that takes most of the time to verify).
Comment #3 October 31st, 2026 at 2:21 am
Hey Scott. At this point most of the Math is being done inside the AI labs. They just cracked the Exponential Time Hypothesis! Are you considering working at OpenAI again? Or Anthropic.
Comment #4 October 31st, 2026 at 5:05 am
Shame that such a nice piece of understanding be achieved thanks to this most perverse of technologies: the whiteboard ! Don’t you have proper, academic-looking, chalks and blackboards in Berkeley and Austin ?
More seriously: would you consider peer-pressuring Dana to a guest post on the experience of decoding the original AI write-up ? The topic is very far from my field so I probably would not benefit from the technical lecture. However I think it is of interest to the community at large if at least the first few people who grapple with the open AI dump recount informally their experience. Might be helpful to me if I finally find the time/motivation to attack some of the papers that are closer to me …
Comment #5 October 31st, 2026 at 9:50 am
Scott#2,
Doesn’t it count as novel coming up with ” totally alien new error-correcting code”, with emphasis on “alien”. Does it imply it would have taken an Einstien to come up with this mind bending code ?
Comment #6 October 31st, 2026 at 9:56 am
Thank you for doing this Scott! The YouTube video is appreciated 🙂
Comment #7 October 31st, 2026 at 10:17 am
Chris Malili #3: Sure, I’d consider working with a frontier AI lab again if I felt like I’d be making a positive difference, contributing to safety rather than merely accelerating capabilities, and it was something I couldn’t do on the outside, and the logistics worked, etc. Right now, though, I like being in academia and feel like I can do almost everything I want to do here, while also being able to speak much more freely! As an example, I don’t feel any compulsion to be the first person to prompt an AI to solve some major open math problem. Who cares which person is first? I’m more interested in understanding what comes out, which is slower work that academics can do and are doing as we speak.
Comment #8 October 31st, 2026 at 10:20 am
Nicolas Rougerie #4: At UT, I managed to choose an office for myself with a blackboard! Alas, mostly whiteboards in our building though.
Comment #9 October 31st, 2026 at 11:04 am
Prasanna #5: I don’t know that Einstein ever cared about hardness of approximation or error-correcting codes. 😀
What we know is that Dana, Subhash, Johan Hastad, Dor, etc all failed to come up with this code, although they’re perfectly able to understand it once they see it.
Comment #10 October 31st, 2026 at 11:56 am
Scott #9 “What we know is that Dana, Subhash, Johan Hastad, Dor, etc all failed to come up with this code, although they’re perfectly able to understand it once they see it.”
But if pundits so expert on devising and figuring out codes and algorithms are only able to understand what an AI agent is capable of cracking after the latter has released its proof of longstanding conjectures it means there is an uncrossable gap between what human agents can now do as deeply involved and prepared as they can be and AI agents can now demonstrate, succeeding in solving problems mathematicians, computer theorists, physicists etc can only set up, being unable to fix and decode them. Hence, from now on human agents (mathematicians, computer theorists, physicists etc) can exclusively live into sort of a niche where they’re gonna no more problem solvers, only problem prompters.
Comment #11 October 31st, 2026 at 12:14 pm
Andy Pezzi #10: Even before AI, for almost all the problems you cared about, it would be someone else solving them, not you, and then your role would “only” be to understand the solution and then think about what else might be done with the ideas.
But yes, AI has now made that even more our role, as opposed to finding the actual proofs. Welcome to the Mathocalypse.
Comment #12 October 31st, 2026 at 5:24 pm
Scott #8 nice getting the blackboard but you’ve REALLY made it when you also get the primo chalk.
https://mathoverflow.net/a/26274