Shtetl-Optimized " Blog Archive " Spreading the Gospel of Theoretical Computer Science to an Omega(1) Fraction of Humanity: My Trevisan Award Acceptance Speech at STOC

Shtetl-Optimized

The Blog of Scott Aaronson

If you take nothing else from this blog: quantum computers won't<br>solve hard problems instantly by just trying all solutions in parallel.<br>Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education!-->

" 50 Years of Aumann’s Agreement Theorem

Spreading the Gospel of Theoretical Computer Science to an Omega(1) Fraction of Humanity: My Trevisan Award Acceptance Speech at STOC

Take that, Shtetl-Optimized haters of the world!

With longtime friend and colleague Salil Vadhan, as well as Luca Trevisan’s widower Junce Zhang, at the STOC banquet on Tuesday, before I was given half an hour to try to make people laugh

Spreading the Gospel of Theoretical Computer Science to an Ω(1) Fraction of Humanity (Or, How We Can Do Like the Physicists)<br>Scott Aaronson’s Trevisan Award Acceptance Speech<br>Salt Lake City, Utah, June 23, 2026

Thank you so much! It’s one of the highlights of my life, frankly, to accept the first-ever Luca Trevisan Award for Expository Work in Theoretical Computer Science—because of, firstly, what this entire STOC community means to me, but also what Luca Trevisan in particular meant to me. Luca was one of the main people who taught me complexity theory—first at an IAS summer school in 2000, then at UC Berkeley, where I took two of his courses and TA’ed for him. As a member of my dissertation committee, Luca once stood on a street corner in San Francisco to meet my friend to sign the signature page of my thesis, as I struggled to get the thing in by the deadline. Later, Luca’s theoretical computer science blog, In Theory, bounced off of my blog.

I wish Luca were here now. But knowing him as well as I did for a quarter century, I feel like I know what he’d say if he learned that I had received the inaugural prize that bears his name. I imagine he’d slap his forehead and say "Seriously, there was no other option??" But I’d like to think that he’d eventually reconcile himself to the choice!

By the way, I noticed that in the committee’s prize announcement, which I found so moving, they added a special paragraph at the end that basically said, "please don’t imagine that to win this prize in the future, you need to behave the way Aaronson behaves. You can just write beautiful textbooks or survey articles or whatnot, and be normal and sane."

The foundation of my career is that I realized 25 years ago that there were better theoretical computer scientists than me—like many in this room, or like Ryan Williams or Andris Ambainis, both of whom I knew at the time. Certainly there were better quantum physicists than me. There were better writers, better expositors, better performers. On the other hand, if you looked specifically at the intersection of computational complexity and quantum physics and standup comedy, that was just this totally uncontested territory!

I’ll let you in on a secret: pretty much everything I’ve done for decades has just been drawing out one joke. That joke is, basically, "computer scientists they be like this, but physicists they be like that." The physicists they be like [exaggerated doofus voice] "duhhhh, NP, what’s that stand for? Not Polynomial?" See, but then there’s also a Rodney Dangerfield aspect to it, because it’s like, how come we never get as much respect as the physicists get? (Though when we do get that respect, I confess that I complain all the more, because then I lose my shtick…)

It’s true that the physicists have certain built-in advantages. They had Einstein, Stephen Hawking, the atom bomb—and just the fact that they’re ultimately talking about, or trying to talk about, the world that we can see and touch. A black hole is an actual place that you could visit, even though I wouldn’t recommend it. But physicists also have much better names for things than we do. I mean, black hole? Big Bang? Quark? Gluon? Supersymmetry? Dark matter?

Meanwhile, what names have we got? TFNP. NC1. And worst of all, PP. These are names that you want to flush down the toilet. But also, the concept of a zero-knowledge protocol, or a two-source extractor, just inherently take longer to explain to people than the concept of a particle, or even a field—even though the latter also turn out to be extremely abstract and mathematical when you push on them. Ask a physicist what a particle is, they’ll tell you that it’s an irreducible representation of the Poincaré group. See, but people think they know what a particle is, it’s just a tiny little hard sphere that moves around, and that’s good enough for them.

So then, how can we win the grand popularity contest against the physicists? How can we, as I put it in my title, spread the gospel of CS theory to a constant fraction of the human race? In my view, the first step is to reframe who we are and what we’re about....