2026-11-09 05:44:31
The “For Dummies” Version (apologies for not including this earlier):
We now, of course, live in age where longstanding open problems in quantum computing theory (and all theoretical computer science, and all math) are dropping like flies, to the extent that there’s no way I could possibly do a post on each and every bombshell. But I can’t exactly avoid the Aaronson-Ambainis Conjecture, given that my name is on it, and that I cared about the answer to this one (back in 2019, I even blogged about an attempted solution that ultimately turned out to be fallacious).
For those tuning in from home, the AA Conjecture, which Andris and I posed back in 2009, says that every bounded degree-d polynomial p:{0,1}n→[0,1] in n Boolean variables, with constant variance, has some variable whose influence is at least 1/poly(d). The reason Andris and I cared about this conjecture is that, as we proved, it implies that there’s no superpolynomial advantage of quantum query complexity over classical query complexity for decision problems that works on most Boolean inputs. Or, in terms of complexity classes, that there’s no hope of separating P from BQP relative to a random oracle, without proving P≠BQP or something of the kind in the unrelativized world. This would finally answer a question of Fortnow and Rogers from 1998.
The connection between quantum algorithms and polynomials came from the famous 1998 paper of Beals et al., which showed that, if Q is a quantum algorithm that makes T queries to an oracle X, then Pr[Q(X) accepts] can be written as a multivariate real polynomial p(X) in the bits of X, of degree at most 2T. The proof of my and Andris’s result is then simply this: take the polynomial p, find in it a variable of influence at least 1/poly(T), and query that variable, and keep repeating until there’s no longer such an influential variable—at which point, by assumption, p is nearly a constant polynomial, which means you’ve learned whether Q accepts with high probability over X. This provides a classical simulation of the quantum algorithm Q, which makes poly(T) queries to the oracle X and which works for most X’s.
The AA Conjecture caught on to an extent Andris and I couldn’t have predicted. Some who worked on it barely even cared about the implication for quantum computing, and just wanted to solve the problem about polynomials! There were, I’m both proud and sorry to report, Fourier analysis experts and grad students who oriented their whole research programs around trying to prove AA, with lots of proofs of special cases, some of them very recent. A proof of full AA was one of the last remaining open problems in quantum query complexity that everyone seemed to agree was centrally important. I was surprised, honestly, to see it missing from OpenAI’s Mathocalypse dump a few weeks ago. Surely they tried it, so was it really so much harder than all the problems that were solved?
Now a startup called Physical Superintelligence has announced a proof of the AA Conjecture, specifically showing that there’s a variable of influence at least ~1/d6, which they say they obtained using their proprietary research harness on an internal Claude model. (What role the harness played, compared to the internal model, is something I don’t know.) The effort was led by David Turturean and Jim Halverson at PSI. They actually let me know about this several weeks ago, but I had to keep it secret until the announcement late last week.
I haven’t yet understood the proof, although I hope to. In the meantime, though, I believe the proof is correct for two reasons. Firstly, there’s a Lean certificate, and secondly, human experts (I’m no longer an expert on my own conjecture!) have already gone over it and understood it. In fact, there’s already a beautiful-looking exposition written by Guy Blanc of MIT and Jordan Docter, Carmen Strassle, and Li-Yang Tan of Stanford, which looks like a perfect starting point for those seeking to go much deeper. Or, for those seeking to go only slightly deeper, PSI’s blog post on the advance is sufficiently well-written that it saves me from the need to write too much here.
Alas, as reported by Ashley Montanaro, there were the usual forehead-banging misconceptions about what this result means for quantum computing. So for example, Pedro Domingos of U. of Washington blasted out to his 137,000 X followers that the proof means that “the dream of quantum supremacy is dead.” The truth, as Pedro knows perfectly well (or easily could know), is that it rules out one particular type of quantum supremacy (namely, for yes-or-no problems relative to random oracles) that we’d already conjectured didn’t exist anyway. It doesn’t undermine any form of quantum supremacy that we did conjecture to exist! It has zero effect, for example, on Shor’s factoring algorithm, which uses a highly non-random (periodic) oracle for the key internal step. It has zero effect on the simulation of quantum physics and chemistry, which generally doesn’t depend on oracle algorithms at all. Even just relative to random oracles, the Yamakawa-Zhandry breakthrough from 2022 dramatically underscored that, if we switch our attention from decision problems to other kind of problems (in Yamakawa and Zhandry’s case, to NP search problems), then exponential quantum speedups do become possible. Anyway, this was sufficiently intellectually dishonest on Pedro’s part that it makes me disinclined to take him seriously about anything ever again.
If you’re wondering how I feel about the proof of AA—well, much like my wife Dana with the Unique Games Conjecture, it’s many different emotions at once.
Anyway, huge congratulations to David Turturean and Jim Halverson, to Physical Superintelligence, and of course to Claude on this achievement!
2026-11-06 01:48:44
As everyone knows, this week was a (an?) historic one for the State of Texas and for the United States as a whole—because this is the week when my wife Dana finally gave a 3-hour public lecture on OpenAI’s recent proof of the Unique Games Conjecture! Thanks so much to the nearly 200 people who joined us in person or via Zoom, and to the staff of UT Austin’s CS department for pulling the event together on short notice. Video will be up on YouTube as soon as we can manage it.
But also, yes, there was an election.
I remember that, when Dana and I moved to Texas in the summer of 2016, we were excited to be a small part of what seemed at the time like Texas’s impending transformation into a cosmopolitan blue state.
And now the prophecy is finally being fulfilled. But so many strange and harrowing things have happened in the interim, that I feel like Murph when her father finally returns to her at the end of the movie Interstellar.
So it turns out that, indeed, the Democrats could’ve easily recaptured both houses of Congress without any need to sell their souls to the likes of Hasan Piker or Abdul El-Sayed. And now the keffiyeh-clad revolutionaries will claim a mandate directly from the people, to put to the sword all the evil landlords and techbros and kulaks and bourgeoisie and (obviously) Zionists, and thereby finally usher in the utopia that failed the first 10,000 times it was tried. I see them as more likely to inspire a Republican comeback in 2028 (as unlikely as it seems this week) than to achieve their stated goals.
For please remember that the socialist firebrands massively underperformed more moderate Democrats on Tuesday—it looks like the socialists were merely lifted up by the same tide of justified anti-MAGA rage. Yes, in the US and across the Western world, some university humanities departments continue to churn out young people who’d see my family’s slaughter as an inspiring (or at least deeply understandable) act of revolutionary justice, and who vote on that basis. By and large, though, the American voters simply belatedly realized that Trump is a charlatan who was never going to deliver anything he promised, and also they wanted cheaper gas.
The Allied victory over Nazi Germany was glorious, it called for parades and dancing in the street, and it was 3,000% earned by Nazi behavior if anything in human history ever was. It left only one tiny problem for the future—namely that, within the winning coalition, the fans of liberal democracy, science, and Enlightenment still needed to confront the Stalinists, whose evil rivaled even the Nazis’, yet who believed their fanatical ideology to be the one vindicated by events. Why was I so often thinking about that these past couple days?
There was, of course, also a big election in Israel. Given the results, I pray that Gadi Eisenkot finds some way to form a coalition, or at least soft coalition, with Israel’s Arab parties, since that’s clearly what it will now take finally to topple Netanyahu, a man whose corruption (like Trump’s or Ken Paxton’s) knows no bounds. I’m under no illusions that this step would do anything to appease the hundreds of millions of protesters around the world whose true demand (as they’ll explain if you ask them) never had anything to do with Israeli policies or Gaza or the West Bank or Bibi Netanyahu, but was always simply that Israel cease to exist—that Israel’s Jews either “go back to Poland” or the other countries where their grandparents were murdered or expelled, or preferably just die, as on October 7.
Nevertheless, I pray for a coalition of moderate Israeli Jews and Arabs, firstly because it’s morally right, secondly because it’s politically expedient, and thirdly because it will impress on at least some fair-minded observers the enormity of the moral chasm here—that, whereas the Arab countries expelled or murdered virtually all of their Jews, the State of Israel not only tolerates its Arab minority but gives it the right to vote and to wield power.
Whatever else one can say, Israel’s Arabs have been sufficiently loyal to their nation that, on October 7, Hamas murdered them right along with the Jews, treating them as Zionist collaborators and traitors to Islam. I’d like to see that loyalty rewarded with a role in Israel’s governing coalition.
As is becoming standard practice with my political posts, I’m closing the comments—because life is short, and these days, the overwhelming majority of comments that I get on posts like this one, whichever ideological axe they’re grinding, are not ones that engender in me even minimal respect for their authors. I apologize to those who would’ve actually pursued a thoughtful dialogue with me or others had I left the comments open—to all five of you, or however many righteous men of Sodom there might be.
2026-11-01 05:40:33
Boooooo! What spooooky times we now live in, with AI rapidly advancing in capabilities and solving more and more major open math problems!
So it seems like a perfect occasion to share yet another podcast. I know I’ve been dropping them like every day, but this is a special one, with Brian Greene for his World Science Festival, recorded in-person when I visited Columbia University a week ago. Note that we don’t talk about OpenAI’s refutation of the Exponential Time Hypothesis because the announcement of that was still two days in the future!
Bonus Addition From Just This Morning (Nov. 3): Another podcast, about quantum computing, foundations of quantum mechanics, AI, consciousness, and I forget what else … this one with writer Robert Wright, whose book The Moral Animal made a huge impression on me back when I was 13 years old!
2026-10-31 07:27:34
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.
2026-10-27 06:03:37
As always, I strongly recommend 2x speed, which compensates somewhat for my verbal infelicities!
New! More podcasts keep dropping! This one is with the AI alignment researcher Roman Yampolskiy, about … well, AI alignment, plus the Mathocalypse, plus quantum computing, plus whether the universe is a simulation, and I forget what else! Man do the YouTube comments make me despair of humanity though.
Another one that recently dropped, with Sophia Aryan:
The title Curt put next to my head could’ve been in reference to many, many things! But sorry, he just mean AI. He and I start with the Mathacre, of course, but then we get onto the firewall paradox and then Curt starts asking about computational complexity and the Second Law, and then about Integrated Information Theory.
Ah, and another one that just dropped! Man’s Search for Meaning podcast (recorded in-person in Austin), with Yannick Bernard, who asked me about quantum computing, AI, my personal story, grade-skipping, antisemitism, and I don’t even remember what else. I didn’t refuse to answer anything. (Note: this one was recorded over the summer, which is why I so weirdly omit the latest AI math breakthroughs!)
OK, despite the title of this post, short break from “The Topic.” Here’s an absolute masterpiece of mathematical exposition, from the “Polylog” YouTube channel, which tells the story of the determination of Busy Beaver values through spectacular animations. I play cameo roles in the video, although I embarrass myself (as the video silently points out) by transposing two digits in the value of BB(5)…!
Just for old times’ sake, a short podcast about quantum computing with Danny Li.
And, coming soon (not on YouTube quite yet): a conversation about the Mathacre with celebrated physics popularizer (and character on The Big Bang Theory) Brian Greene, recorded in-person in NYC during my recent trip to speak in the math department at Columbia University!
And to preempt the inevitable comments about it: yes, my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n)). Even as we struggle to digest the previous courses, the endless buffet continues!
2026-10-26 05:54:26
Someone writing an article for the Israeli press about “people abroad who love Israel but might be worried” emailed me the following questions:
“1. What is something about Israel that you admire/appreciate over the years?
2. What are you worried the most about Israel these days?”
So I replied as follows:
“It’s hard to know where to start with either of your questions! But briefly:
Tiny Israel standing up for itself, against an often hostile and unjust world, is a huge part of what’s given me the self-confidence to stand up for myself in my own life. That was true even before I had visited Israel or spent significant time there, gazed across the desert at the still-clear ruins of the Roman siege of Masada, staggered overwhelmed out of Yad Vashem into the sunlight of Jerusalem, tasted the hummus or pomegranate juice or ice cream with blended fruit, befriended or had academic collaborations with dozens of Israelis, or married an Israeli woman.
My fear is merely the ‘obvious’ one — that, in response to the staggering hostility directed against the ‘Jew among the nations,’ Israel will become more and more belligerent, isolated, and right-wing. It will get demographically overwhelmed by those who don’t want to work or serve in the army, while hundreds of thousands of secular educated Israelis leave. It will be internally divided almost to the point of civil war. It will repudiate the liberal-democratic vision of Herzl and Ben-Gurion, of world-class universities and making the deserts bloom, for the swaggering, theocratic vision of Smotrich and Ben-Gvir, of chasing Palestinians from their olive groves. It will become more and more like the hateful caricature of itself that the anti-Israel people in the West always imagined. And then, having been internally weakened in all of these ways, it will finally be destroyed by its external enemies, who will never have rested the whole time, who never once wavered in their dream of a second Holocaust.
I hope and pray that in the upcoming election, the Israeli voters make optimistic choices that repudiate these fears.”
As I’ll do more and more with political posts, I’m leaving the comments off. Why? Because my remaining life is too short to spend it battling an endless parade of trolls and griefers, leftists and rightists and just nihilists, who might or might not be AI.