The Mathocalypse

From the archives of Shtetl-Optimized The Blog of Scott Aaronson

Crucial Disclaimer: If you remember nothing else from this site, remember this: quantum computers are not magic bullets that solve all hard problems instantly via parallel processing.

Additionally, I highly recommend reading Zvi Mowshowitz's definitive guide on reforming K-12 education!

The Day the Robots "Cooked" the Mathematicians

I recently realized the gravity of our current situation through a story shared by my friend, Omer Reingold. He recounted a moment where his 9-year-old son was relentlessly teasing his mother, the complexity theorist Dana Moshkovitz:

"Mommy, I heard you got cooked! I heard a robot solved the math problem you spent your whole career on! OOF!"

While the boy was being a bit of a brat, his assessment was accurate. Regardless of whether this news brings you joy, despair, or anger, we have just witnessed one of the most pivotal moments in the history of mathematics.

OpenAI recently released 372 massive results. This drop was guided by an advisory board featuring luminaries like Edward Witten and Timothy Gowers. Among these breakthroughs was a proof of Subhash Khot’s Unique Games Conjecture (UGC)—a problem Dana has spent her entire professional life pursuing.

What is the UGC?

In essence, the UGC suggests that a vast array of optimization problems are truly $\text{NP-hard}$ . Specifically, it implies that even if you only seek an approximation slightly better than what is achievable via semidefinite programming relaxation (a primary tool in the field), the problem remains computationally intractable.

The Verification Gap

We believe the proof is correct, primarily because it comes with a Lean certificate (a formal verification), as do several other results in the batch. However, there is a catch: no human actually understands these proofs yet. We are currently in a frantic race to decipher them.

To give you a glimpse of that struggle, here are some of the texts Dana sent me regarding the UGC proof:

"It reads like it was written by someone on psychedelics."

"It name-drops previous research without explaining how it bypasses known impossibility results. The writing is so atrocious that you literally cannot read it without the help of an AI."

"I used Astra to synthesize the soundness and completeness claims for the noise gadget because they were scattered randomly across the paper."

"They've found direct optimal $\text{NP}$ -hardness of approximation proofs for things like Max Cut and all CSPs, completely bypassing the UGC."

"The proof introduces a bizarre, alien code with a noise test. It's not the short code or the long code—it's some otherworldly craziness. I still suspect a more natural proof exists using the half space code."

"The citations are often irrelevant or just confusing."

"The future might be a world where humans provide the creative vision and AI handles the implementation and verification."

Emotional Fallout and Silver Linings

Dana is likely feeling a whirlwind of emotions. However, there are two comforting perspectives:

Vindication: She always believed the UGC was true, even when many of her peers were skeptical.
Solidarity: Every single person in theoretical computer science, math, and mathematical physics who cares about solving "crisply-stated problems" is now in the same boat.

Treasures from "Aladdin's Cave"

Beyond the UGC, the OpenAI release contained a staggering array of results. Here are the ones I am most focused on:

Result	Significance	Detail/Nuance
$L = BPL$	Major derandomization	Proves probabilistic logspace and deterministic logspace are identical.
$\text{Fourier Transform}$	Breaking a 60-year barrier	Integer multiplication now takes less than $O(n \log n)$ . Specifically: $O(n \log 0.9999999999999 n)$ .
$\text{Unitary Synthesis}$	Positive solution	For any $n$ -qubit unitary $U$ , there's a classical oracle $A$ allowing $U$ to be implemented in quantum poly-time.
$\text{Parity} \notin \text{QAC}^0$	Quantum complexity	Solves a major question open since 1999.
$\text{Query Complexity}$	$\approx 4\text{th}$ -power separation	A gap between randomized and quantum query complexity for total Boolean functions (previously known to be between 2 and 6).
$\text{Sensitivity}$	Superquadratic separation	A gap between sensitivity and block sensitivity.
$\text{Matrix Mult.}$	$O(n^{9/4})$	A rational exponent achieved via a totally new approach.
$\text{Permanent}$	$\Omega(n^3)$ lower bound	Improves the previous quadratic bound on determinantal complexity.
$\text{Perfect Matchings}$	Approx. counting	A randomized polytime algorithm for general graphs.

A Note on Unitary Synthesis

The result on the Unitary Synthesis Problem (which Greg Kuperberg and I posed in 2007) is the opposite of what most of us expected. It could have massive implications for $\text{decoding Hawking radiation from black holes}$ , provided we can actually construct the oracle $A$ (which the paper does not explain). My colleague Dakshita Khurana wrote a beautiful post about her years of work on this, having correctly believed in a positive answer.

Final Thoughts

~~The era of the lone human mathematician is over.~~ The era of the human-AI partnership has begun. We have much to learn from the "aliens."

Current Status:

UGC Proven
$L=BPL$ Proven
Understand how the hell the AI did it