OpenAI publishes 372 math results, including a proof of the Unique Games Conjecture
- OpenAI released 372 mathematical results at once, among them a proof of Subhash Khot's Unique Games Conjecture, issued on the recommendation of an advisory group that includes Timothy Gowers and Edward Witten.
- Some of the results ship with a Lean certificate, but no human had understood the UGC proof when Aaronson wrote. Dana Moshkovitz, who worked on the conjecture for her whole career, called the paper unreadable without AI help and said the proof invents a recursive noise test built on "some alien craziness" rather than the long or short code.
- The same batch includes L = BPL (derandomizing logspace), the Fourier transform and integer multiplication below O(n log n) for the first time since the 1960s at O(n log^0.9999999999999 n), and a positive solution to the Unitary Synthesis Problem that Aaronson and Greg Kuperberg posed in 2007.
- The UGC implies that many optimization problems are NP-hard to approximate even slightly better than semidefinite programming relaxation gives, so the proof settles a question Moshkovitz never doubted was true while many colleagues did.
- Aaronson says the race to verify the proofs has just started, and Dakshita Khurana wrote about the years she spent on unitary synthesis and her belief in a positive answer when most others expected the opposite.
Hacker News opinions
Agents basically did statistically guided brute forcing. Nothing they produced adds any understanding of anything, and I think it will hurt the field.
That is not a correct description of what the AI did.
Evolution did statistically guided brute forcing too. Doesn't mean biology has no value.
You can tell this wasn't written by an AI from the first sentence. My 8 year old talks exactly like that at the dinner table. I asked ChatGPT to write an 8 year old roasting his mom about being replaced by AI and got awkward Millennial-flavored lines, nothing close.
I added 'use current trendy lingo' and the output got less mechanical, one line even said 'cooked' and another had 'negative aura'. Then HN insta-flagged my comment for being AI, which has never happened to me before.
I liked the metaphor of a climber teleported to the top of a fog shrouded mountain. The teleporter exists now, so we use it to reach more peaks. There's no going back to a world without it.
The issue is ownership. We have no means of distributing the knowledge the AI produces or rewarding the people who could help, and all symbolic and numeric reasoning for economic purposes is heading to AI.
I had this conversation with my PhD students. I am 100% sure all of their problems can be solved by publicly available models now, I solved one myself in 15 minutes. The defence is going to be a test of understanding, not a test of publication count.
Then maybe they should target more ambitious results now. This racing spirit in academia is insane, get in before the door closes.
What's with all these results that are technically below O(n log n) but only by 0.0000000001? Feels like the machine did the absolute minimum to beat the previous mark.
You just run it again and again. And often the 2 in the exponent is the conjectured minimum, so anything below it breaks a theoretical limit.
For FFT, integer multiplication and 3SUM we've had the same natural algorithms for decades and assumed they were optimal. An O(n(log n)^0.99999) algorithm shows that optimality conjecture is false. Same shape as Strassen.
Tell that to the matrix multiplication people who spent years going from n^2.3728596 to n^2.371866, and then OpenAI blew past them at n^2.25.
Maybe big O is just deceptive here. These fast algorithms usually have constants that make them worthless in practice.
The irony is something born out of science eating that science.
Boaz Barak said the purpose of science is to make boring what was once exciting. Whitehead said the same thing in 1911 about civilization advancing by extending the operations we can perform without thinking.
That psychedelics quote is the part nobody else covered. Wading through it sounds like reading someone else's messy code that happens to produce the right output.
And that is the fear, these proofs out-compete attempts at human-readable ones. Maybe we end up with math influencers annotating them for the rest of us.