- The STOC’2026 accepted papers list is out. It seems to me that there’s an emperor’s bounty of amazing stuff this year. I felt especially gratified to see the paper on the determination of BusyBeaver(5) on the list, reflecting a broad view of what theory of computing is about.
- There’s a phenomenal profile of Henry Yuen in Quanta magazine. Henry is now one of the world leaders of quantum complexity theory, involved in breakthroughs like MIP*=RE and now pioneering the complexity theory of quantum states and unitary transformations (the main focus of this interview). I’m proud that Henry tells Quanta that learned about the field in 2007 or 2008 from a blog called … what was it again? … Shtetl-Optimized? I’m also proud that I got to help mentor Henry when he was a PhD student of my wife Dana Moshkovitz at MIT. Before I read this Quanta profile, I didn’t even know the backstory about Henry’s parents surviving and fleeing the Cambodian genocide, or about Henry growing up working in his parents’ restaurant. Henry never brought any of that up!
- See Lance’s blog for an obituary of Joe Halpern, a pioneer of the branch of theoretical computer science that deals with reasoning about knowledge (e.g., the muddy children puzzle), who sadly passed away last week. I knew Prof. Halpern a bit when I was an undergrad at Cornell. He was a huge presence in the Cornell CS department who’ll be sorely missed.
- UT Austin has announced the formation of a School of Computing, which will bring together the CS department (where I work) with statistics, data science, and several other departments. Many of UT’s peer institutions have recently done the same. Naturally, I’m excited for what this says about the expanded role of computing at UT going forward. We’ll be looking to hire even more new faculty than we were before!
- When I glanced at the Chronicle of Higher Education to see what was new, I learned that researchers at OpenAI had proposed a technical solution, called “watermarking,” that might help tackle the crisis of students relying on AI to write all their papers … but that OpenAI had declined to deploy that solution. The piece strongly advocates a legislative mandate in favor of watermarking LLM outputs, and addresses some of the main counterarguments to that position.
- For those who can’t get enough podcasts of me, here are the ones I’ve done recently. Quantum: Science vs. Mythology on the Peggy Smedley Show. AI Alignment, Complexity Theory, and the Computability of Physics, on Alexander Chin’s Philosophy Podcast. And last but not least, What Is Quantum Computing? on the Robinson Erhardt Podcast.
- Also, here’s an article that quotes me entitled “Bitcoin needs a quantum upgrade. So why isn’t it happening?” Also, here’s a piece that interviews me in Investor’s Business Daily, entitled “Is quantum computing the next big tech shift?” (I have no say over these titles.)
This entry was posted
on Friday, February 20th, 2026 at 12:31 am and is filed under Announcements, Complexity, Quantum, Speaking Truth to Parallelism.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.
All comments are treated, by default, as personal missives to me, Scott Aaronson---with no expectation either that they'll appear on the blog or that I'll reply to them.
Follow
Comment #1 February 20th, 2026 at 1:36 am
I took a Quantum Computing class from Henry at Columbia, so that’s really cool! I had no idea he was such a top researcher.
Comment #2 February 20th, 2026 at 9:15 am
Reviewing the STOC’26 accepted papers list, it’s really cool just to see *how many* papers relate to quantum computing – “Simon’s revenge” from STOC’94(?)
I wonder – could that history repeat itself nowadays? Could there be a preprint submitted to STOC’26 that is rejected because no one really understands it or its significance except for maybe one committee member (“Qeter Thor”) who unsuccessfully champions its acceptance and later writes a brilliant and revolutionary work bringing the ideas in the rejected paper to life to solve some crucial and well-studied problem; after 30-some odd years in STOC’52 a large number of papers have something to do the revolution brought about by the ideas from 2026…?
Or have the dynamics of publishing changed so much since ’94 that brilliant ideas will have ways of bubbling up to the top, even without something like STOC/FOCS publication?
Comment #3 February 20th, 2026 at 10:23 am
Mark Spinelli #2: I’m virtually certain that there was great stuff rejected from this STOC because no one recognized its significance. Reviewing is hard even when all the reviewers are maximally hardworking and open-minded (which they aren’t always), and while STOC has expanded, the volume of submissions has expanded even more. The good news, or at least hope, is that the overall system works: rejected brilliant stuff will get published somewhere else, just like Simon’s paper was, and people will notice it and build on it, and the original STOC rejection will just be a story for the ages.
Of course we should try to minimize such cases. When I was once on a STOC PC, I was deeply impressed when there was a screaming dispute about one particular paper, with half the PC members saying “we must take this” and the other half saying “no way in hell,” until finally the PC chair stepped in to say, “the very fact that there’s such a passionate dispute means we accept the paper.” That stayed with me forever.
Comment #4 February 20th, 2026 at 11:47 am
Another piece of research news is Chevignard et al extended their residue arithmetic technique from quantum factoring to quantum elliptic curve discrete logarithms: https://eprint.iacr.org/2026/280 .
The space savings is lower than it was for factoring (1.6x instead of 6x) and the Toffoli overhead is again enormous (~5600x), but algorithmic progress continues.
Comment #5 February 20th, 2026 at 8:58 pm
Scott, a dumb MIP*=RE question. RE is uncomputable exactly because (supposing the natural numbers to be incompletely be described by some axioms like ZFC and we can’t say more about them than that) its membership will depend on what model of arithmetic we live in, right? So do the quantum entangled provers know something special about “true” arithmetic that the axioms don’t? Like, CON(ZFC) is independent of ZFC because (supposing ZFC is consistent) there is a nonstandard model of ZFC which in fact contains a proof (of nonstandard size) that 1=0, but there is none in the standard model.
But, I mean, what is really standard anyway? Maybe we live in that “nonstandard” model after all. So can entangled provers convince us that ZFC is inconsistent, because they see that nonstandard proof? Or can they somehow distinguish standard from nonstandard?
Every time anyone says “uncomputable” I wonder what happens with stuff like this.
Comment #6 February 20th, 2026 at 10:53 pm
asdf #5: No, RE is uncomputable simply because the halting problem is in RE, and no Turing machine can solve the halting problem by the famous diagonalization proof. You’re overcomplicating things to even bring ZFC or models of arithmetic into it.
Comment #7 February 22nd, 2026 at 10:02 am
asdf #5: I disagree with Scott #6: The “MIP*=RE” proof can be formalized in ZFC, and probably even in some weaker system, typically Mac Lane set theory (i.e. higher order arithmetics). And the RE in the proof cannot rely on what the “true standard model of natural number arithmetics” would answer, but only on what an unspecified but “given” model of ZFC answers. Since MIP* has access to the same “given” model of ZFC, this is not really a problem.
But it raises the interesting question how the “possible lies” of the “given” model for RE translate into “possible lies” for MIP*. An interesting lie for MIP* could be that the polynomial measuring the runtime uses non-standard numbers. I have not studied the proof in sufficient detail to confirm or deny that MIP* could use that sort of lie. The most boring lie would be that MIP* just stops answering. However, if this “boring lie” would be the only possible way for MIP* to lie, that would actually be extremely interesting.
I now watched:
https://www.youtube.com/watch?v=yrXeAH1gurM
(The Role of Proofs in MIP* = RE | Quantum Colloquium)
https://www.youtube.com/watch?v=3PZBxAT4X24
(Panel Discussion on The Role of Proofs in MIP* = RE | Quantum Colloquium)
The main talk was illuminating and helpful. The panel discussion was a bit too specialized for me, and doesn’t seem to contribute anything to answer my remaining questions with respect to how MIP* could could lie.
Comment #8 February 22nd, 2026 at 11:32 am
gentzen #7: Of course the proof of MIP*=RE should be formalizable in ZFC or even much weaker systems—why wouldn’t it be? But that doesn’t mean we need to talk about the axioms of ZFC, or any other formal system, in order to understand what RE is as a mathematical object—any more than we’d need to do so to understand the set of prime numbers, or a 4-manifold, or any other standard mathematical object. The only reasons to talk about axioms here is if we’re interested in metamathematics, or in formalizing our reasoning process (perhaps with a system like Lean), not for “object-level” reasons.
Comment #9 February 22nd, 2026 at 12:26 pm
Scott #8: The point is that MIP*=RE relativizes to arbitrary models of ZFC. For RE, the “possible lies” of an arbitrary model responsible for the strong dependence of RE (as a countable set of Turing machines) on the model are well understood. For MIP*, it is not yet clear to me how the strong dependence of MIP* (as a countable set of Turing machines) on the model arises.
That the polynomial measuring the runtime uses non-standard numbers is one possibility. It feels unlikely to me, and I guess if I would study the MIP*=RE proof in detail, I would be able to explicitly write down a polynomial measuring the runtime. This would exclude that possibility.
The other mentioned possibility that MIP* just stops answering also feels unlikely to me, but in a different way. It would be a qualitative change in behavior between RE and MIP*, which most proof techniques cannot provoke. It would be the analog of a non-relativizing proof in complexity theory. Since IP = PSPACE was the prototypical non-relativizing proof, it might not be too surprising after all. But knowing whether or not this is the case is interesting, not just metamathematics.
Comment #10 February 22nd, 2026 at 12:34 pm
gentzen #9: The other way of saying that MIP*=RE “relativizes to arbitrary models of ZFC” is that MIP*=RE is just a true mathematical fact, full stop, a fact whose proof ZFC can indeed formalize (but if it couldn’t, then so much the worse for ZFC), and all these considerations that you keep trying to bring in are completely irrelevant. Or rather, they’re no more relevant than they are to any other theorem in any ordinary branch of math. You seem to be confusing mathematical reality itself—e.g., which complexity classes are equal or unequal—with the various formal systems by which we prove aspects of that reality. Sorry, others are welcome to continue this debate but I need to move on.
Comment #11 February 23rd, 2026 at 6:43 am
I believe what gentzen and asdf are getting at is something like this:
Let’s say I have a halting oracle and a pair of entangled provers. MIP*=RE says that anything I can do with the oracle, I can do with the help of the provers, and vice versa.
Now suppose someone surreptitiously replaces my halting oracle with a lying oracle that purports to solve the halting problem but gives the wrong answer as long as ZFC cannot tell the difference.
MIP*=RE was proven in ZFC so it still works: anything I can do with the lying oracle, I can do with the provers. But that means the provers must be lying too—how can they get away with it?
Comment #12 February 23rd, 2026 at 1:17 pm
anon #11: Ah, thanks for translating! That’s another “levels of abstraction” type confusion. Yes, in ZFC you can prove that MIP*=RE, and hence that the MIP* protocol and the HALT oracle will always give you the same answer. You merely can’t always prove what that answer will be — for example, in the case of a Turing machine that halts iff it finds an inconsistency in ZFC. But that has no effect on the equivalence proof.
Comment #13 February 24th, 2026 at 10:29 am
The paradox is that since provers and oracles are demonstrably equal in power, it would very surprising if some oracles could lie but all provers were trustworthy. But that is exactly how we usually think about them: we must take oracles on faith alone but provers are supposedly verifiable by mere mortals.
If ZFC cannot prove the oracle wrong then ZFC must know of a prover interaction that would corroborate the oracle. gentzen (#7, #9) speculates that when the oracle is lying, ZFC’s “interaction that verifies the falsehood” might be a nonstandard one (i.e. our model of ZFC is lying, there is no such interaction) but I don’t think that’s possible. It seems to me that the deceptive interaction has to have the provers secretly bypass their entanglement and talk to each other directly. Mortals cannot know what infinite entanglement truly looks like; we must take it on faith alone that the multiple provers are not colluding.
I’d like to rephrase asdf’s original question (“what is standard anyway?”) like this: If we found (in the physical universe) provers who can successfully carry out the “ZFC is inconsistent” interactive proof, would that “metaphysically prove” that we live in a nonstandard universe, in a way that a lone oracle could not? Per above, obviously not.
I guess the “metaphysical contradiction in ZFC” such provers do give you is that ZFC proves a certain event is very unlikely but when you actually do the experiment, it happens almost every time. Presumably this event is some Bell-inequality-violation style non-signalling correlation rather than something the verifier can freely choose. (It would be pretty interesting if we could have a situation where you say “See! They are cheating! This prover just told me something only the other prover knew.” and all a self-hating nonstandard ZFC can say in the provers’ defense is “That could have been just a coincidence! Try it again and it will stop working eventually.” But no, I believe that if ZFC says it can find no evidence of wrongdoing by the provers, it’s because the provers have actually good excuses for their behavior, even when the provers really are cheating.)
Comment #14 February 24th, 2026 at 4:42 pm
anon #13: Thanks for translating, and for trying to judge how the entangled provers will “most likely” convince us that ZFC is inconsistent (in case ZFC is inconsistent in the given non-standard model of ZFC). I basically agree that this is the “most likely” resolution. (I say “resolution,” but I didn’t use the words “paradox” or “contradiction”. I only used the words “possibility” and “interesting”.)
Because, if the Turing machine only holds after a non-standard number of steps, then the two provers also share a non-standard number of entangled qubits. And this allows them to share more information than we expect, because we expect that they only share finitely many entangled qubits.
asdf #5: “So can entangled provers convince us that ZFC is inconsistent, because they see that nonstandard proof?”
Yes, I believe now that the entangled provers convince us that ZFC is inconsistent.
Comment #15 February 25th, 2026 at 5:04 pm
Scott, Gentzen, anon: thanks everyone!
Comment #16 February 25th, 2026 at 5:09 pm
Meanwhlie, on the AI alignment front, if I understand this, the US defense department is now demanding that Claude have its alignment turned off:
https://www.theguardian.com/us-news/2026/feb/24/anthropic-claude-military-ai
I guess it could be worse. They could ask to have all the alignment work incorporated but shifted into reverse. OTOH maybe they don’t have to bother:
https://www.newscientist.com/article/2516885-ais-cant-stop-recommending-nuclear-strikes-in-war-game-simulations/
Comment #17 February 26th, 2026 at 5:43 pm
Note of correction about the new School of Computing. The third department in the school will be the Department of Information, currently the School of Information. As a school it is not departmentalized. So we wouldn’t say there will be just 3 departments in the school.
Comment #18 February 26th, 2026 at 8:56 pm
Alas the watermarking story is behind a paywall. I wonder if they address the following argument:
Suppose you get all the big guys with frontier models like OpenAI to watermark. Then I could still get my homework done by them, and then afterwards send it through an open source / open weight model I run at home to rewrite to scramble / remove the watermark.
The second model doesn’t have to be very smart, so it’s feasible to run at home.
Comment #19 February 27th, 2026 at 12:31 pm
Nathan T #17: Ok, thanks for the clarification!
Comment #20 February 27th, 2026 at 2:20 pm
Scott,
I know you’re interested in using AI to advance research in fundamental physics and computer science, so I think you’ll really enjoy this.
I recently came across someone who’s been collaborating with ChatGPT on some incredibly ambitious ideas about the foundations of physics. Having talked to him, I can attest that this guy is a serious genius. The work is bold and thought-provoking and it attempts to tackle deep questions around quantum gravity and string theory in a unified way. If he’s right, he’s basically solved string theory and quantum gravity in one fell swoop.
Here’s the paper:
https://github.com/muellerberndt/observer-patch-holography/blob/main/paper/STRING_THEORY.md
And here’s a discussion thread:
https://x.com/muellerberndt/status/2027267719930994744
Given your interest in how AI can expand the boundaries of research and help solve hard problems, I think you’ll find this especially intriguing. Definitely worth a look!
Comment #21 February 28th, 2026 at 7:01 am
Jordan #20: um lol no.
Comment #22 March 5th, 2026 at 10:15 am
“AI Alignment, Complexity Theory, and the Computability of Physics, on Alexander Chin’s Philosophy Podcast. “
Your make-up and wardrobe teams were spot on.
You sometimes look like a caged lion on podcasts because your internal clock speed is much higher than that of your interviewers I think.