Scott Aaronson's Blog, page 7

My Reading Burden

Want some honesty about how I (mis)spend my time? These days, my daily routine includes reading all of the following:

The comments on this blog (many of which I then answer)The Washington Post (“The Post Most” takes me about an hour a day, every day)The New York TimesScott Alexander’s Astral Codex TenZvi Mowshowitz’s Don’t Worry About the Vase (Zvi is so superhumanly prolific that reading him easily takes 12 hours per week … but it’s all good stuff!)Peter Woit’s Not Even Wrong (rarely updated anymore, thankfully for my reading time!)QuilletteThe Free PressMosaicTabletCommentaryPaul Graham’s TwitterDavid Deutsch’s TwitterEliezer Yudkowsky’s TwitterUpdates and comments from my Facebook friends (this can easily take a couple hours per day)The quant-ph arXiv (I scan maybe 50 titles and abstracts per day, and if any papers are relevant to me, read at least their introductions)The science fiction and fantasy novels I read with my kidsWhichever other books I’m currently reading

Many of these materials contain lists of links to other articles, or tweet threads, some of which then take me hours to read in themselves. This is not counting podcasts or movies or TV shows.

While I read unusually quickly, I’d estimate that my reading burden is now at eight hours per day, seven days per week. I haven’t finished reading by the time my kids are back from school or day camp. Now let’s add in my actual job (or two jobs, although the OpenAI one is ending this month, and I start teaching again in two weeks). Add in answering emails (including from fans and advice-seekers), giving lectures, meeting grad students and undergrads, doing Zoom calls, filling out forms, consulting, going on podcasts, reviewing papers, taking care of my kids, eating, shopping, personal hygiene.

As often as not, when the day is done, it’s not just that I’ve achieved nothing of lasting value—it’s that I’ve never even started with research, writing, or any long-term projects. This contrasts with my twenties, when obsessively working on research problems and writing up the results could easily fill my day.

The solution seems obvious: stop reading so much. Cut back to a few hours per day, tops. But it’s hard. The rapid scale-up of AI is a once-in-the-history-of-civilization story that I feel astounded to be living through and compelled to follow, and just keeping up with the highlights is almost a full-time job in itself. The threat to democracy from Trump, Putin, Xi, Maduro, and the world’s other authoritarians is another story that I feel unable to look away from.

Since October 7, though, the once-again-precarious situation of Jews everywhere on earth has become, on top of everything else it is, the #1 drain on my time. It would be one thing if I limited myself to thoughtful analyses, but I can easily lose hours per day doomscrolling through the infinite firehose of strident anti-Zionism (and often, simple unconcealed Jew-hatred) that one finds for example on Twitter, Facebook, and the comment sections of Washington Post articles. Every time someone calls the “Zios” land-stealing baby-killers who deserve to die, my brain insists that they’re addressing me personally. So I stop to ponder the psychology of each individual commenter before moving on to the next, struggle to see the world from their eyes. Would explaining the complex realities of the conflict change this person’s mind? What about introducing them to my friends and relatives in Israel who never knew any other home and want nothing but peace, coexistence, and a two-state solution?

I naturally can’t say that all this compulsive reading makes me happy or fulfilled. Worse yet, I can’t even say it makes me feel more informed. What I suppose it does make me feel is … excused. If so much is being written daily about the biggest controversies in the world, then how can I be blamed for reading it rather than doing anything new?

At the risk of adding even more to the terrifying torrent of words, I’d like to hear from anyone who ever struggled with a similar reading addiction, and successfully overcame it. What worked for you?

My pontificatiest AI podcast ever!

Back in May, I had the honor (nay, honour) to speak at HowTheLightGetsIn, an ideas festival held annually in Hay-on-Wye on the English/Welsh border. It was my first time in that part of the UK, and I loved it. There was an immense amount of mud due to rain on the festival ground, and many ideas presented at the talks and panels that I vociferously disagreed with (but isn’t that the point?).

At some point, interviewer Alexis Papazoglou with the Institute for Art and Ideas ambushed me while I was trudging through the mud to sit me down for a half-hour interview about AI that I’d only vaguely understood was going to take place, and that interview is now up on YouTube. I strongly recommend listening at 2x speed: you’ll save yourself fifteen minutes, I’ll sound smarter, my verbal infelicities will be less noticeable, what’s not to like?

I was totally unprepared and wearing a wrinkled t-shirt, but I dutifully sat in the beautiful chair arranged for me and shot the breeze about AI. The result is actually one of the recorded AI conversations I’m happiest with, the one that might convey the most of my worldview per minute. Topics include:

My guesses about where AI is goingHow I respond to skeptics of AIThe views of Roger Penrose and where I part ways from himThe relevance (or not) of the quantum No-Cloning Theorem to the hard problem of consciousnessWhether and how AI will take over the worldAn overview of AI safety research, including interpretability and dangerous capability evaluationsMy work on watermarking for OpenAI

Last night I watched the video with my 7-year-old son. His comment: “I understood it, and it kept my brain busy, but it wasn’t really fun.” But hey, at least my son didn’t accuse me of being so dense I don’t even understand that “an AI is just a program,” like many commenters on YouTube did! My YouTube critics, in general, were helpful in reassuring me that I wasn’t just arguing with strawmen in this interview (is there even such a thing as a strawman position in philosophy and AI?). Of course the critics would’ve been more helpful still if they’d, y’know, counterargued, rather than just calling me “really shallow,” “superficial,” an “arrogant poser,” a “robot,” a “chattering technologist,” “lying through his teeth,” and “enmeshed in so many faulty assumptions.” Watch and decide for yourself!

Meanwhile, there’s already a second video on YouTube, entitled Philosopher reacts to ‘OpenAI expert Scott Aaronson on consciousness, quantum physics, and AI safety.’   So I opened the video, terrified that I was about to be torn a new asshole. But no, this philosopher just replays the whole interview, occasionally pausing it to interject comments like “yes, really interesting, I agree, Scott makes a great point here.”

Update: You can also watch the same interviewer grill General David Petraeus, at the same event in the same overly large chairs.

My “Never-Trump From Here to Eternity” FAQ

Q1: Who will you be voting for in November?

A: Kamala Harris (and mainstream Democrats all down the ballot), of course.

Q2: Of course?

A: If the alternative is Trump, I would’ve voted for Biden’s rotting corpse. Or for Hunter Biden. Or for…

Q3: Why can’t you see this is just your Trump Derangement Syndrome talking?

A: Look, my basic moral commitments remain pretty much as they’ve been since childhood. Namely, that I’m on the side of reason, Enlightenment, scientific and technological progress, secular government, pragmatism, democracy, individual liberty, justice, intellectual honesty, an American-led peaceful world order, preservation of the natural world, mitigation of existential risks, and human flourishing. (Crazy and radical, I know.)

Only when choosing between candidates who all espouse such values, do I even get the luxury of judging them on any lower-order bits. Sadly, I don’t have that luxury today. Trump’s values, such as they are, would seem to be “America First,” protectionism, vengeance, humiliation of enemies, winning at all costs, authoritarianism, the veneration of foreign autocrats, and the veneration of himself. No amount of squinting can ever reconcile those with the values I listed before.

Q4: Is that all that’s wrong with him?

A: No, there are also the lies, and worst of all the “Big Lie.” Trump is the first president in US history to conspire to overturn the results of an election. He was serious! He very nearly succeeded, and probably would have, had Mike Pence been someone else. It’s now inarguable that Trump rejects the basic rules of our system, or “accepts” them only when he wins. We’re numb from having heard it so many times, but it’s a big deal, as big a deal as the Civil War was.

Q5: Oh, so this is about your precious “democracy.” Why do you care? Haven’t you of all people learned that the masses are mostly idiots and bullies, who don’t deserve power? As Curtis Yarvin keeps trying to explain to you, instead of “democracy,” you should want a benevolent king or dictator-CEO, who could offer a privileged position to the competent scientists like yourself.

A: Yeah, so how many examples does history furnish where that worked out well? I suppose you might make a partial case for Napoleon, or Ataturk? More to the point: even if benevolent, science-and-reason-loving authoritarian strongmen are possible in theory, do you really expect me to believe that Trump could be one of them? I still love how Scott Alexander put it in 2016:

Can anyone honestly say that Trump or his movement promote epistemic virtue? That in the long-term, we’ll be glad that we encouraged this sort of thing, that we gave it power and attention and all the nutrients it needed to grow? That the road to whatever vision of a just and rational society we imagine, something quiet and austere with a lot of old-growth trees and Greek-looking columns, runs through LOCK HER UP?

I don’t like having to vote for the lesser of two evils. But at least I feel like I know who it is.

Q6: But what about J. D. Vance? He got his start in Silicon Valley, was championed by Peter Thiel, and is obviously highly intelligent. Doesn’t he seem like someone who might listen to and empower tech nerds like yourself?

A: Who can say what J. D. Vance believes? Here are a few choice quotes of his from eight years ago:

I’m obviously outraged at Trump’s rhetoric, and I worry most of all about how welcome Muslim citizens feel in their own country. But I also think that people have always believed crazy shit (I remember a poll from a few years back suggesting that a near majority of democratic voters blame ‘the Jews’ for the financial crisis). And there have always been demagogues willing to exploit the people who believe crazy shit.

The more white people feel like voting for trump, the more black people will suffer. I really believe that.

[Trump is] just a bad man. A morally reprehensible human being.

To get from that to being Trump’s running mate is a Simone-Biles-like feat of moral acrobatics. Vance reminds me of the famous saying by L. Ron Hubbard from his pre-Dianetics days: “If a man really wants to make a million dollars, the best way would be to start his own religion.” (And I feel like Harris’s whole campaign strategy should just be to replay Vance’s earlier musings in wall-to-wall ads while emphasizing her agreement with them.) No, Vance is not someone I trust to share my values, if he has values at all.

Q7: What about the other side’s values, or lack thereof? I mean, don’t you care that the whole Democratic establishment—including Harris—colluded to cover up that Biden was senile and cognitively unfit to be president now, let alone for another term?

A: Look, we’ve all seen what happens as a relative gets old. It’s gradual. It’s hard for anyone to say at which specific moment they can no longer drive a car, or be President of the United States, or whatever. This means that I don’t necessarily read evil intent into the attempts to cover up Biden’s decline—merely an epic, catastrophic failure of foresight. That failure of foresight itself would’ve been a huge deal in normal circumstances, but these are not normal circumstances—not if you believe, as I do, that the alternative is the beginning of the end of a 250-year-old democratic experiment.

Q8: Oh stop being so melodramatic. What terrible thing happened to you because of Trump’s first term? Did you lose your job? Did fascist goons rough you up in the street?

A: Well, my Iranian PhD student came close to having his visa revoked, and it became all but impossible to recruit PhD students from China. That sucked, since I care about my students’ welfare like I care about my own. Also, the downfall of Roe v. Wade, which enabled Texas’ draconian new abortion laws, made it much harder for us to recruit faculty at UT Austin. But I doubt any of that will impress you. “Go recruit American students,” you’ll say. “Go recruit conservative faculty who are fine with abortion being banned.”

The real issue is that Trump was severely restrained in his first term, by being surrounded by people who (even if, in many cases, they started out loyal to him) were also somewhat sane and valued the survival of the Republic. Alas, he learned from that, and he won’t repeat that mistake the next time.

Q9: Why do you care so much about Trump’s lies? Don’t you realize that all politicians lie?

A: Yes, but there are importantly different kinds of lies. There are white lies. There are scheming, 20-dimensional Machiavellian lies, like a secret agent’s cover story (or is that only in fiction?). There are the farcical, desperate, ever-shifting lies of the murderer to the police detective or the cheating undergrad to the professor. And then there are the lies of bullies and mob bosses and and populist autocrats, which are special and worse.

These last, call them power-lies, are distinguished by the fact that they aren’t even helped by plausibility. Often, as with conspiracy theories (which strongly overlap with power-lies), the more absurd the better. Obama was born in Kenya. Trump’s crowd was the biggest in history. The 2020 election was stolen by a shadowy conspiracy involving George Soros and Dominion and Venezuela.

The central goal of a power-lie is just to demonstrate your power to coerce others into repeating it, much like with the Party making Winston Smith affirm 2+2=5, or Petruchio making Katharina call the sun the moon in The Taming of the Shrew. A closely-related goal is as a loyalty test for your own retinue.

It’s Trump’s embrace of the power-lie that puts him beyond the pale for me.

Q10: But Scott, we haven’t even played our “Trump” card yet. Starting on October 7, 2023, did you not witness thousands of your supposed allies, the educated secular progressives on “the right side of history,” cheer the sadistic mass-murder of Jews—or at least, making endless excuses for those who did? Did this not destabilize your entire worldview? Will you actually vote for a party half of which seems at peace with the prospect of your family members’ physical annihilation? Or will you finally see who your real friends now are: Arkansas MAGA hillbillies who pray for your people’s survival?

A: Ah, this is your first slash that’s actually drawn blood. I won’t pretend that the takeover of part of the US progressive coalition by literal Hamasniks hasn’t been one of the most terrifying experiences of my life. Yes, if I had to be ruled by either (a) a corrupt authoritarian demagogue or (b) an idiot college student chanting for “Intifada Revolution,” I’d be paralyzed. So it’s lucky that I don’t face that choice! I get to vote, once more, for a rather boring mainstream Democrat—alongside at least 70% of American Jews. The idea of Harris as an antisemite would be ludicrous even if she didn’t have a Jewish husband or wasn’t strongly considering a pro-Israel Jew as her running mate.

Q11: Sure, Kamala Harris might mouth all the right platitudes about Israel having a right to defend itself, but she’ll constantly pressure Israel to make concessions to Hamas and Hezbollah. She’ll turn a blind eye to Iran’s imminent nuclearization. Why don’t you stay up at night worrying that, if you vote for a useful idiot like her, you’ll have Israel’s annihilation and a second Holocaust on your conscience forever?

A: Look, oftentimes—whenever, for example, I’m spending hours reading anti-Zionists on Twitter—I feel like there’s no limit to how intensely Zionist I am. On reflection, though, there is a limit. Namely, I’m not going to be more Zionist than the vast majority of my Israeli friends and colleagues—the ones who served in the IDF, who in some cases did reserve duty in Gaza, who prop up the Israeli economy with their taxes, and who will face the consequences of whatever happens more directly than I will. With few exceptions, these friends despise the Trump/Bibi alliance with white-hot rage, and they desperately want more moderate leadership in both countries.

Q12: Suppose I concede that Kamala is OK on Israel. We both know that she’s not the future of the Democratic Party, any more than Biden is. The future is what we all saw on campuses this spring. “Houthis Houthis make us proud, turn another ship around.” How can you vote for a party whose rising generation seems to want you and your family dead?

A: Let me ask you something. When Trump won in 2016, did that check the power of the campus radicals? Or as Scott Alexander prophesied at the time, did it energize and embolden them like nothing else, by dramatically confirming their theology of a planet held hostage by the bullying, misogynistic rich white males? I fundamentally reject your premise that, if I’m terrified of crazy left-wing extremists, then a good response is to vote for the craziest right-wing extremists I can find, in hopes that the two will somehow cancel each other out. Instead I should support a coherent Enlightenment alternative to radicalism, or the closest thing to that available.

Q13: Even leaving aside Israel, how can you not be terrified by what the Left has become? Which side denounced you on social media a decade ago, as a misogynist monster who wanted all women to be his sex slaves? Which side tried to ruin your life and career? Did we, the online rightists, do that? No. We did not. We did nothing worse to you than bemusedly tell you to man up, grow a pair, and stop pleading for sympathy from feminists who will hate you no matter what.

A: Back in 2017, when Kamala Harris was in the Senate, her office invited me to DC to meet with them to provide advice about the National Quantum Initiative Act, which Kamala was then spearheading. Kamala herself sent regrets that she couldn’t meet me, because she had to be at the Kavanaugh hearings. I have (nerdy, male) friends who did meet her about tech policy and came away with positive impressions.

And, I dunno, does that sound like someone who wants me dead for the crime of having been born a nerdy heterosexual male? Or having awkwardly and ineptly asked women on dates, including one who became my wife? OK, maybe Amanda Marcotte wants me dead for those crimes. Maybe Arthur Chu does (is he still around?). Good that they’re not running for president then.

Q14: Let me try one more time to show you how much your own party hates you. Which side has been at constant war against the SAT and other standardized tests, and merit-based college admissions, and gifted programs, and academic tracking and acceleration, and STEM magnet schools, and every single other measure by which future young Scott Aaronsons (and Saket Agrawals) might achieve their dreams in life? Has that been our side, or theirs?

A: To be honest, I haven’t seen the Trump or Harris campaigns take any position on any of these issues. Even if they did, there’s very little that the federal government can do: these battles happen in individual states and cities and counties and universities. So I’ll vote for Harris while continuing to advocate for what I think is right in education policy.

Q15: Can you not see that Kamala Harris is a vapid, power-seeking bureaucratic machine—that she has no fixed principles at all? For godsakes, she all but condemned Biden as a racist in the 2020 primary, then agreed to serve as his running mate!

A: I mean, she surely has more principles than Vance does. As far as I can tell, for example, she’s genuinely for abortion rights (as I am). Even if she believed in nothing, though, better a cardboard cutout on which values that I recognize are written, than a flesh-and-blood person shouting values that horrify me.

Q16: What, if anything, could Republicans do to get you to vote for them?

A: Reject all nutty conspiracy theories. Fully, 100% commit to the peaceful transfer of power. Acknowledge the empirical reality of human-caused climate change, and the need for both technological and legislative measures to slow it and mitigate its impacts. Support abortion rights, or at least a European-style compromise on abortion. Republicans can keep the anti-wokeness stuff, which actually seems to have become their defining issue. If they do all that, and also the Democrats are taken over by frothing radicals who want to annihilate the state Israel and abolish the police … that’s, uhh, probably the point when I start voting Republican.

Q17: Aha, so you now admit that there exist conceivable circumstances that would cause you to vote Republican! In that case, why did you style yourself “Never-Trump From Here to Eternity”?

A: Tell you what, the day Republicans repudiate authoritarianism and start respecting election outcomes, I’ll admit that my title was hyperbolic and bad.

Q18: In the meantime, will you at least treat us Trump supporters with civility and respect?

A: Not only does civil disagreement not compromise any of my values, it is a value to which I think we should all aspire. And to whatever extent I’ve fallen short of that ideal—even when baited into it—I’m sorry and I’ll try to do better. Certainly, age and experience have taught me that there’s hardly anyone so far gone that I can’t find something on which I agree with them, while disagreeing with most of the rest of the world.

New comment policy

With yesterday’s My Prayer, for the first time I can remember in two decades of blogging, I put up a new post with the comments section completely turned off. I did so because I knew my nerves couldn’t handle a triumphant interrogation from Trumpist commenters about whether, in the wake of their Messiah’s (near-)blood sacrifice on behalf of the Nation, I’d at last acquiesce to the dissolution of America’s constitutional republic and its replacement by the dawning order: one where all elections are fraudulent unless the MAGA candidate wins, and where anything the leader does (including, e.g., jailing his opponents) is automatically immune from prosecution. I couldn’t handle it, but at the same time, and in stark contrast to the many who attack from my left, I also didn’t care what they thought of me.

With hindsight, turning off comments yesterday might be the single best moderation decision I ever made. I still got feedback on what I’d written, on Facebook and by email and text message and in person. But this more filtered feedback was … thoughtful. Incredibly, it lowered the stress that I was feeling rather than raising it even higher.

For context, I should explain that over the past couple years, one or more trolls have developed a particularly vicious strategy against me. Below my every blog post, even the most anodyne, a “new” pseudonymous commenter shows up to question me about the post topic, in what initially looks like a curious, good-faith way. So I engage, because I’m Scott Aaronson and that’s what I do; that’s a large part of the value I can offer the world.

Then, only once a conversation is underway does the troll gradually ratchet up the level of crazy, invariably ending at some place tailor-made to distress me (for example: vaccines are poisonous, death to Jews and Israel, I don’t understand basic quantum mechanics or computer science, I’m a misogynist monster, my childhood bullies were justified and right). Of course, as soon as I’ve confirmed the pattern, I send further comments straight to the trash. But the troll then follows up with many emails taunting me for not engaging further, packed with farcical accusations and misreadings for me to rebut and other bait.

Basically, I’m now consistently subjected to denial-of-service attacks against my open approach to the world. Or perhaps I’ve simply been schooled in why most people with audiences of thousands or more don’t maintain comment sections where, by default, they answer everyone! And yet it’s become painfully clear that, as long as I maintain a quasi-open comment section, I’ll feel guilty if I don’t do this.

So without further ado, I hereby announce my new comment policy. Henceforth all comments to Shtetl-Optimized will be treated, by default, as personal missives to me—with no expectation either that they’ll appear on the blog or that I’ll reply to them.

At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I’ll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I’ll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet.

The new policy starts now, in the comment section of this post. To the many who’ve asked me for this over the years, you’re welcome!

My Prayer

It is the duty of good people, always and everywhere, to condemn, reject, and disavow the use of political violence.

Even or especially when evildoers would celebrate the use of political violence against us.

It is our duty always to tell the truth, always to play by the rules — even when evil triumphs by lying, by sneeringly flouting every rule.

It appears to be an iron law of Fate that whenever good tries to steal a victory by evil means, it fails. This law is so infallible that any good that tries to circumvent it thereby becomes evil.

When Sam Bankman-Fried tries to save the world using financial fraud — he fails. Only the selfish succeed through fraud.

When kind, nerdy men, in celibate desperation, try to get women to bed using “Game” and other underhanded tactics — they fail. Only the smirking bullies get women that way.

Quantum mechanics is false, because its Born Rule speaks of randomness.

But randomness can’t explain why a bullet aimed at a destroyer of American democracy must inevitably miss by inches, while a bullet aimed at JFK or RFK or MLK or Gandhi or Rabin must inevitably meet its target.

Yet for all that, over the millennia, good has made actual progress. Slavery has been banished to the shadows. Children survive to adulthood. Sometimes altruists become billionaires, or billionaires altruists. Sometimes the good guy gets the girl.

Good has progressed not by lucky breaks — for good never gets lucky breaks — but only because the principles of good are superior.

There’s a kind of cosmic solace that could be offered even to the Jewish mother in the gas chamber watching her children take their last breaths, though the mother could be forgiven for rejecting it.

The solace is that good will triumph — if not in the next four years, then in the four years after that.

Or if not in four, then in a hundred.

Or if not in a hundred, then in a thousand.

Or if not in the entire history of life in on this planet, then on a different planet.

Or if not in this universe, then in a different universe.

Let us commit to fighting for good using good methods only. Fate has decreed in any case that, for us, those are the only methods that work.

Let us commit to use good methods only even if it means failure, heartbreak, despair, the destruction of democratic institutions and ecosystems multiplied by a thousand or a billion or any other constant — with the triumph of good only in the asymptotic limit.

Good will triumph, when it does, only because its principles are superior.

Endnote: I’ve gotten some pushback for this prayer from one of my scientific colleagues … specifically, for the part of the prayer where I deny the universal validity of the Born rule. And yet a less inflammatory way of putting the same point would simply be: I am not a universal Bayesian. There are places where my personal utility calculations do a worst-case analysis rather than averaging over possible futures for the world.

Endnote 2: It is one thing to say, never engage in political violence because the expected utility will come out negative. I’m saying something even stronger than that. Namely, even if the expected utility comes out positive, throw away the whole framework of being an expected-utility maximizer before you throw away that you’re never going to endorse political violence. There’s a class of moral decisions for which you’ve allowed to, even to be commended for, using expected-utility calculations, and this is outside that class.

Endnote 3: If you thought that Trump’s base was devoted before, now that the MAGA Christ-figure has sacrificed his flesh — or come within a few inches of doing so — on behalf of the Nation, they will go to the ends of the earth for him, as much as any followers did for any ruler in human history. Now the only questions, assuming Trump wins (as he presumably will), are where he chooses to take his flock, and what emerges in the aftermath for what we currently call the United States. I urge my left-leaning American friends to look into second passports. Buckle up, and may we all be here to talk about it on the other end.

Quantum developments!

Perhaps like the poor current President of the United States, I can feel myself fading, my memory and verbal facility and attention to detail failing me, even while there’s so much left to do to battle the nonsense in the world. I started my career on an accelerated schedule—going to college at 15, finishing my PhD at 22, etc. etc.—and the decline is (alas) also hitting me early, at the ripe age of 43.

Nevertheless, I do seem to remember that this was once primarily a quantum computing blog, and that I was known to the world as a quantum computing theorist. And exciting things continue to happen in quantum computing. In fact, just on last night’s quant-ph arXiv mailing, there were two…

First, a company in the UK called Oxford Ionics has announced that it now has a system of trapped-ion qubits in which it’s prepared two-qubit maximally entangled states with 99.97% fidelity. If true, this seems extremely good. Indeed, it seems better than the numbers from bigger trapped-ion efforts, and quite close to the ~99.99% that you’d want for quantum fault-tolerance. But maybe there’s a catch? Will they not be able to maintain this kind of fidelity when doing a long sequence of programmable two-qubit gates on dozens of qubits? Can the other trapped-ion efforts actually achieve similar fidelities in head-to-head comparisons? Anyway, I was surprised to see how little attention the paper got on SciRate. I look forward to hearing from experts in the comment section.

Second, a new paper by Schuster, Haferkamp, and Huang gives a major advance on k-designs and pseudorandom unitaries. Roughly speaking, the paper shows that even in one dimension, a random n-qubit quantum circuit, with alternating brickwork layers of 2-qubit gates, forms a “k-design” after only O(k polylog k log n) layers of gates. Well, modulo one caveat: the “random circuit” isn’t from the most natural ensemble, but has to have some of its 2-qubit gates set to the identity, namely those that straddle certain contiguous blocks of log n qubits. This seems like a purely technical issue—how could randomizing those straddling gates make the mixing behavior worse?—but future work will be needed to address it. Notably, the new upper bound is off from the best-possible k layers by only logarithmic factors. (For those tuning in from home: a k-design informally means a collection of n-qubit unitaries such that, from the perspective of degree-k polynomials, choosing a unitary randomly from the collection looks the same as choosing randomly among all n-qubit unitary transformations—i.e., from the Haar measure.)

Anyway, even in my current decrepit state, I can see that such a result would have implications for … well, all sorts of things that quantum computing and information theorists care about. Again I welcome any comments from experts!

The Zombie Misconception of Theoretical Computer Science

In Michael Sipser’s Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this:

Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)

The correct answer is that yes, f is computable. Why? Because the constant 1 function is computable, and so is the constant 0 function, so if f is one or the other, then it’s computable.

If you’re still tempted to quibble, then consider the following parallel question:

Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?

The answer is again yes: even though n hasn’t been completely mathematically specified, it’s been specified enough for us to say that it’s prime (just like if we’d said, “n is an element of the set {3,5}; is n prime?”). Similarly, f has been specified enough for us to say that it’s computable.

The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.

Dozens of times in the past 25 years, I’ve gotten some variant on the following question, always with the air that I’m about to bowled over by its brilliance:

Could the P versus NP question itself be NP-hard, and therefore impossible to solve?

Every time I get this one, I struggle to unpack the layers of misconceptions. But for starters: the concept of “NP-hard” applies to functions or languages, like 3SAT or Independent Set or Clique or whatnot, all of which take an input (a Boolean formula, a graph, etc) and produce a corresponding output. NP-hardness means that, if you had a polynomial-time algorithm to map the inputs to the outputs, then you could convert it via reductions into a polynomial-time algorithm for any language or function in the class NP.

P versus NP, by contrast, is an individual yes-or-no question. Its answer (for all we know) could be independent of the Zermelo-Fraenkel axioms of set theory, but there’s no sense in which the question could be uncomputable or NP-hard. Indeed, a fast program that correctly answers the P vs. NP question trivially exists:

If P=NP, then the program prints “P=NP.”If P≠NP, then the program prints “P≠NP.”

In the comments of last week’s post on the breakthrough determination of Busy Beaver 5, I got several variants on the following question:

What’s the smallest n for which the value of BB(n) is uncomputable? Could BB(6) already be uncomputable?

Once again, I explained that the Busy Beaver function is uncomputable, but the concept of computability doesn’t apply to individual integers like BB(6). Indeed, whichever integer k turns out to equal BB(6), the program “print k” clearly exists, and it clearly outputs that integer!

Again, we can ask for the smallest n such that the value of BB(n) is unprovable in ZF set theory (or some other system of axioms)—precisely the question that Adam Yedidia and I did ask in 2016 (the current record stands at n=745, improving my and Adam’s n=8000). But every specific integer is “computable”; it’s only the BB function as a whole that’s uncomputable.

Alas, in return for explaining this, I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue.

So, I’ve come to think of this as the Zombie Misconception of Theoretical Computer Science: this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems. (Or, relatedly: the constant conflation of the uncomputability of the halting problem with Gödel incompleteness. While they’re closely related, only Gödel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.)

Anyway, I’m writing this post mostly just so that I have a place to link the next time this pedagogical zombie rises from its grave, muttering “UNCOMPUTABLE INTEGERRRRRRS….” But also so I can query my readers: what are your ideas for how to keep this zombie down?

BusyBeaver(5) is now known to be 47,176,870

The news these days feels apocalyptic to me—as if we’re living through, if not the last days of humanity, then surely the last days of liberal democracy on earth.

All the more reason to ignore all of that, then, and blog instead about the notorious Busy Beaver function! Because holy moly, what news have I got today. For lovers of this super-rapidly-growing sequence of integers, I’ve honored to announce the biggest Busy Beaver development that there’s been since 1983, when I slept in a crib and you booted up your computer using a 5.25-inch floppy. That was the year when Allen Brady determined that BusyBeaver(4) was equal to 107. (Tibor Radó, who invented the Busy Beaver function in the 1960s, quickly proved with his student Shen Lin that the first three values were 1, 6, and 21 respectively. The fourth value was harder.)

Only now, after an additional 41 years, do we know the fifth Busy Beaver value. Today, an international collaboration called bbchallenge is announcing that it’s determined, and even formally verified using the Coq proof system, that BB(5) is equal to 47,176,870—the value that’s been conjectured since 1990, when Heiner Marxen and Jürgen Buntrock discovered a 5-state Turing machine that runs for exactly 47,176,870 steps before halting, when started on a blank tape. The new bbchallenge achievement is to prove that all 5-state Turing machines that run for more steps than 47,176,870, actually run forever—or in other words, that 47,176,870 is the maximum finite number of steps for which any 5-state Turing machine can run. That’s what it means for BB(5) to equal 47,176,870.

For more on this story, see Ben Brubaker’s superb article in Quanta magazine, or bbchallenge’s own announcement. For more background on the Busy Beaver function, see my 2020 survey, or my 2017 big numbers lecture, or my 1999 big numbers essay, or the Googology Wiki page, or Pascal Michel’s survey.

The difficulty in pinning down BB(5) was not just that there are a lot of 5-state Turing machines (16,679,880,978,201 of them to be precise, although symmetries reduce the effective number). The real difficulty is, how do you prove that some given machine runs forever? If a Turing machine halts, you can prove that by simply running it on your laptop until halting (at least if it halts after a “mere” ~47 million steps, which is child’s-play). If, on the other hand, the machine runs forever, via some never-repeating infinite pattern rather than a simple infinite loop, then how do you prove that? You need to find a mathematical reason why it can’t halt, and there’s no systematic method for finding such reasons—that was the great discovery of Gödel and Turing nearly a century ago.

More precisely, the Busy Beaver function grows faster than any function that can be computed, and we know that because if a systematic method existed to compute arbitrary BB(n) values, then we could use that method to determine whether a given Turing machine halts (if the machine has n states, just check whether it runs for more than BB(n) steps; if it does, it must run forever). This is the famous halting problem, which Turing proved to be unsolvable by finite means. The Busy Beaver function is Turing-uncomputability made flesh, a finite function that scrapes the edge of infinity.

There’s also a more prosaic issue. Proofs that particular Turing machines run forever tend to be mind-numbingly tedious. Even supposing you’ve found such a “proof,” why should other people trust it, if they don’t want to spend days staring at the outputs of your custom-written software?

And so for decades, a few hobbyists picked away at the BB(5) problem. One, who goes by the handle “Skelet”, managed to reduce the problem to 43 holdout machines whose halting status was still undetermined. Or maybe only 25, depending who you asked? (And were we really sure about the machines outside those 43?)

The bbchallenge collaboration improved on the situation in two ways. First, it demanded that every proof of non-halting be vetted carefully. While this went beyond the original mandate, a participant named “mxdys” later upped the standard to fully machine-verifiable certificates for every non-halting machine in Coq, so that there could no longer be any serious question of correctness. (This, in turn, was done via “deciders,” programs that were crafted to recognize a specific type of parameterized behavior.) Second, the collaboration used an online forum and a Discord server to organize the effort, so that everyone knew what had been done and what remained to be done.

Despite this, it was far from obvious a priori that the collaboration would succeed. What if, for example, one of the 43 (or however many) Turing machines in the holdout set turned out to encode the Goldbach Conjecture, or one of the other great unsolved problems of number theory? Then the final determination of BB(5) would need to await the resolution of that problem. (We do know, incidentally, that there’s a 23-state Turing machine that encodes Goldbach.)

But apparently the collaboration got lucky. Coq proofs of non-halting were eventually found for all the 5-state holdout machines.

As a sad sidenote, Allen Brady, who determined the value of BB(4), apparently died just a few days before the BB(5) proof was complete. He was doubtful that BB(5) would ever be known. The reason, he wrote in 1988, was that “Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.”

Maybe I should say a little at this point about what the 5-state Busy Beaver—i.e., the Marxen-Buntrock Turing machine that we now know to be the champion—actually does. Interpreted in English, the machine iterates a certain integer function g, which is defined by

g(x) = (5x+18)/3 if x = 0 (mod 3),g(x) = (5x+22)/3 if x = 1 (mod 3),g(x) = HALT if x = 2 (mod 3).

Starting from x=0, the machine computes g(0), g(g(0)), g(g(g(0))), and so forth, halting if and if it ever reaches … well, HALT. The machine runs for millions of steps because it so happens that this iteration eventually reaches HALT, but only after a while:

0 → 6 → 16 → 34 → 64 → 114 → 196 → 334 → 564 → 946 → 1584 → 2646 → 4416 → 7366 → 12284 → HALT.

(And also, at each iteration, the machine runs for a number of steps that grows like the square of the number x.)

Some readers might be reminded of the Collatz Conjecture, the famous unsolved problem about whether, if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. As Scott Alexander would say, this is not a coincidence because nothing is ever a coincidence. (Especially not in math!)

It’s a fair question whether humans will ever know the value of BB(6). Pavel Kropitz discovered, a couple years ago, that BB(6) is at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 (i.e., 10 raised to itself 15 times). Obviously Kropitz didn’t actually run a 6-state Turing machine for that number of steps until halting! Instead he understood what the machine did—and it turned out to apply an iterative process similar to the g function above, but this time involving an exponential function. And the process could be proven to halt after ~15 rounds of exponentiation.

Meanwhile Tristan Stérin, who coordinated the bbchallenge effort, tells me that a 6-state machine was recently discovered that “iterates the Collatz-like map {3x/2, (3x-1)/2} from the number 8 and halts if and only if the number of odd terms ever gets bigger than twice the number of even terms.” This shows that, in order to determine the value of BB(6), one would first need to prove or disprove the Collatz-like conjecture that that never happens.

Basically, if and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7).

I first learned about the BB function in 1996, when I was 15 years old, from a book called The New Turing Omnibus by A. K. Dewdney.  From what I gather, Dewdney would go on to become a nutty 9/11 truther.  But that’s irrelevant to the story.  What matters was that his book provided my first exposure to many of the key concepts of computer science, and probably played a role in my becoming a theoretical computer scientist at all.

And of all the concepts in Dewdney’s book, the one I liked the most was the Busy Beaver function. What a simple function! You could easily explain its definition to Archimedes, or Gauss, or any of the other great mathematicians of the past. And yet, by using it, you could name definite positive integers (BB(10), for example) incomprehensibly larger than any that they could name.

It was from Dewdney that I learned that the first four Busy Beaver numbers were the unthreatening-looking 1, 6, 21, and 107 … but then that the fifth value was already unknown (!!), and at any rate at least 47,176,870. I clearly remember wondering whether BB(5) would ever be known for certain, and even whether I might be the one to determine it. That was almost two-thirds of my life ago.

As things developed, I played no role whatsoever in the determination of BB(5) … except for this. Tristan Stérin tells me that reading my survey article, The Busy Beaver Frontier, was what inspired him to start and lead the bbchallenge collaboration that finally cracked the problem. It’s hard to express how gratified that makes me.

Why care about determining particular values of the Busy Beaver function? Isn’t this just a recreational programming exercise, analogous to code golf, rather than serious mathematical research?

I like to answer that question with another question: why care about humans landing on the moon, or Mars? Those otherwise somewhat arbitrary goals, you might say, serve as a hard-to-fake gauge of human progress against the vastness of the cosmos. In the same way, the quest to determine the Busy Beaver numbers is one concrete measure of human progress against the vastness of the arithmetical cosmos, a vastness that we learned from Gödel and Turing won’t succumb to any fixed procedure. The Busy Beaver numbers are just … there, Platonically, as surely as 13 was prime long before the first caveman tried to arrange 13 rocks into a nontrivial rectangle and failed. And yet we might never know the sixth of these numbers and only today learned the fifth.

Anyway, huge congratulations to the bbchallenge team on their accomplishment. At a terrifying time for the world, I’m happy that, whatever happens, at least I lived to see this.

“Never A Better Time to Visit”: Our Post-October-7 Trip to Israel

Dana, the kids, and I got back to the US last week after a month spent in England and then Israel. We decided to visit Israel because … uhh, we heard there’s never been a better time.

We normally go every year to visit Dana’s family and our many friends there, and to give talks. Various well-meaning friends suggested that maybe we should cancel or postpone this year—given, you know, the situation. To me, though, the situation felt like all the more reason to go. To make Israel seem more and more embattled, dangerous, isolated, abnormal, like not an acceptable place to visit (much less live), in order to crater its economy, demoralize its population, and ultimately wipe it from the face of earth … that is explicitly much of the world’s game plan right now, laid out with shocking honesty since October 7 (a day that also showed us what the “decolonization” will, concretely, look like). So, if I oppose this plan, then how could I look myself in the mirror while playing my tiny part in it? Shouldn’t I instead raise a middle finger to those who’d murder my family, and go?

Besides supporting our friends and relatives, though, I wanted to see the post-October-7 reality for myself, rather than just spending hours per day reading about it on social media. I wanted to form my own impression of the mood in Israel: fiercely determined? angry? hopeless? just carrying on like normal?

Anyway, in two meeting-packed weeks, mostly in Tel Aviv but also in Jerusalem, Haifa, and Be’er Sheva, I saw stuff that could support any of those narratives. A lot was as I’d expected, but not everything. In the rest of this post, I’ll share eleven observations:

(1) This presumably won’t shock anyone, but in post-October-7 Israel, you indeed can’t escape October 7. Everywhere you look, on every building, in every lobby, hanging from every highway overpass, there are hostage posters and “Bring Them Home Now” signs and yellow ribbons—starting at the airport, where every single passenger is routed through a long corridor of hostage posters, each one signed and decorated by the hostage’s friends and family. It sometimes felt as though Yad Vashem had expanded to encompass the entire country. Virtually everyone we talked to wanted to share their stories and opinions about the war, most of all their depression and anger. While there was also plenty of discussion about quantum error mitigation and watermarking of large language models and local family events, no one even pretended to ignore the war.

(2) Having said that, the morning after we landed, truthfully, that leapt out at me wasn’t anything to do with October 7, hostages, or Gaza. It was the sheer number of children playing outside, in any direction you looked. Full, noisy playgrounds on block after block. It’s one thing to know intellectually that Israel has by far the highest birthrate of any Western country, another to see it for yourself. The typical secular family probably has three kids; the typical Orthodox family has more. (The Arab population is of course also growing rapidly, both in Israel and in the West Bank and Gaza.) New apartment construction is everywhere you look in Tel Aviv, despite building delays caused by the war. And it all seems perfectly normal … unless you’ve lived your whole life in environments where 0.8 or 1.2 children per couple is the norm.

This, of course, has giant implications for anyone interested in Israel’s future. It’s like, a million Israeli leftists could get fed up and flee to the US or Canada or Switzerland, and Israel would still have a large and growing Jewish population—because having a big family is “just what people do” in a state that was founded to defy the Holocaust. In particular: anyone who dreams of dismantling the illegal, settler-colonial, fascist Zionist ethnostate, and freeing Palestine from river to sea, had better have some plan for what they’re going to do with all these millions of young Jews, who don’t appear to be going anywhere.

(3) The second thing I noticed was the heat—comparable to the Texas summer heat that we try to escape when possible. Because of the roasting sun, our own two pampered offspring mostly refused to go outside during daytime, and we mostly met friends indoors. I more than once had the dark thought that maybe Israel will survive Hamas, Hezbollah, Iran, and its own Jewish extremists … only to be finished off in the end (along with much of the rest of the planet) by global warming. I wonder whether Israel will manage to engineer its way out of the crisis, as it dramatically engineered its way out of its water crisis via desalination. The Arab petrostates have been trying to engineer their way out of the Middle East’s increasingly Mercury-like climate, albeit with decidedly mixed results.

(4) But nu, what did our Israeli friends say about the war? Of course it’s a biased sample, because our friends are mostly left-wing academics and tech workers. But, at risk of overgeneralizing: they’re unhappy. Very, very unhappy. As for Bibi and his far-right yes-men? Our friends’ rage at them was truly a sight to behold. American progressives are, likely, mildly irked by Trump in comparison. Yes, our friends blame Bibi for the massive security and intelligence failures that allowed October 7 to happen. They blame him for dragging out the war to stave off elections. They blame him for empowering the contemptible Ben-Gvir and Smotrich. They blame him for his failure to bring back the remaining hostages. Most of all, they blame him for refusing even to meet with the hostage families, and more broadly, for evading responsibility for all that he did wrong, while arrogating credit for any victories (like the rescue of Noa Argamani).

(5) One Israeli friend offered to take me along to the giant anti-Bibi rally that now happens every Saturday night in Azrieli Center in Tel Aviv. (She added that, if I left before 9pm, it would reduce the chances of the police arresting me.) As the intrepid blogger-investigator I am, of course I agreed.

While many of the protesters simply called for new elections to replace Netanyahu (a cause that I 3000% support), others went further, demanding a deal to free the hostages and an immediate end to the war (even if, as they understood, that would leave Hamas in power).

Watching the protesters, smelling their pot smoke that filled the air, I was seized by a thought: these Israeli leftists actually see eye-to-eye with the anti-Israel American leftists on a huge number of issues. In a different world, they could be marching together as allies. Except, of course, for one giant difference: namely, the Tel Aviv protesters are proudly waving Israeli flags (sometimes modified to add anti-Bibi images, or to depict the Star of David “crying”), rather than burning or stomping on those flags. They’re marching to save the Israel that they know and remember, rather than to destroy it.

(6) We did meet one ultra-right-wing (and Orthodox) academic colleague. He was virtually the only person we met on this trip who seemed cheerful and optimistic about Israel’s future. He brought me to his synagogue to celebrate the holiday of Shavuot, while he himself stood guarding the door of the synagogue with a gargantuan rifle (his volunteer duty since October 7). He has six kids.

(7) Again and again, our secular liberal friends told us they’re thinking about moving from Israel, because if the Bibi-ists entrench their power (and of course the demographics are trending in that direction), then they don’t see that the country has any worthwhile future for them or their children. Should this be taken more seriously than the many Americans who promise that this time, for real, they’ll move to Canada if Trump wins? I’m not sure. I can only report what I heard.

(8) At the same time, again and again I got the following question from Israelis (including the leftist ones): how bad is the situation for Jews in the US? Have the universities been taken over by militant anti-Zionists, like it shows in the news? I had to answer: it’s complicated. Because I live my life enbubbled in the STEM field of computer science, surrounded by friends and colleagues of all backgrounds, ethnicities, religions, and political opinions who are thoughtful and decent (otherwise, why would they be my friends and colleagues?), I’m able to live a very nice life even in the midst of loud protesters calling to globalize the intifada against my family.

If, on the other hand, I were in a typical humanities department? Yeah, then I’d be pretty terrified. My basic options would be to (a) shut up about my (ironically) moderate, middle-of-the-road opinions on Israel/Palestine, such as support for the two-state solution; (b) live a miserable and embattled existence; or (c) pack up and move, for example to Israel.

An astounding irony right now is that, just as Israeli leftists are talking about moving from Israel, some of my American Jewish friends have talked to me about moving to Israel, to escape a prejudice that they thought died with their grandparents. I don’t know where the grass is actually greener (or is it brown everywhere?). Nor do I know how many worriers will actually follow through. What’s clear is that, both in Israel and in the diaspora, Jews are feeling an existential fear that they haven’t felt for generations.

(9) Did I fear for my own family’s safety during the trip? Not really. Maybe I should have. When we visited Haifa, we found that GPS was scrambled all across northern Israel, to make targeting harder for Hezbollah missiles. As a result, we couldn’t use Google Maps, got completely lost driving, and had to change plans with our friends. For the first time, now I really feel angry at Hezbollah: they made my life worse and it’s personal!

The funniest part, though, was how the scrambling was implemented: when you opened Google Maps anywhere in the north, it told you that you were in Beirut. It then dutifully gave you walking or driving directions to wherever you were going in Israel, passing through Syria close to Damascus (“warning: this route passes through multiple countries”).

(10) The most darkly comical thing that I heard on the entire trip: “oh, no, I don’t object in the slightest if the anti-Zionists want to kill us all. I only object if they want to kill us because of an incorrect understanding of the relevant history.” Needless to say, this was a professor.

(11) After my two-week investigation, what grand insight can I offer about Israel’s future? Not much, but maybe this: I think we can definitively rule out the scenario where Israel, having been battered by October 7, and bracing itself to be battered worse by Hezbollah, just sort of … withers away and disappears. Yes, Israel might get hotter, more crowded, more dangerous, more right-wing, and more Orthodox. But it will stay right where it is, unless and until its enemies destroy it in a cataclysmic war. You can’t scare people away, break their will, if they believe they have nowhere else on the planet to go. You can only kill them or else live next to them in peace, as the UN proposed in 1947 and as Oslo proposed in the 1990s. May we live to see peace.

Anyway, on that pleasant note, time soon to tune in to the Trump/Biden debate! I wonder who these two gentlemen are, and what they might stand for?

Luca Trevisan (1971-2024)

(See here for Boaz Barak’s obituary)

Luca Trevisan, one of the world’s leading theoretical computer scientists, has succumbed to cancer in Italy, at only 52 years old. I was privileged to know Luca for a quarter-century, first as my complexity theory and cryptography professor at UC Berkeley and as a member of my dissertation committee, and then as a friend and colleague and fellow CS theory blogger.

I regret that I learned of the seriousness of Luca’s condition only a few days ago. So yesterday morning I wrote him a farewell email, under the impression that, while he was now in hospice care, he had at least a few more weeks. Alas, he probably never saw it. So I’m hereby making the email into a memorial post, with small changes mostly to protect people’s privacy.

Dear Luca,

Dana, the kids, and I were traveling in Israel for the past two weeks, when I received the shocking and sad news that this might be my last chance to write to you.

At risk of stating the obvious — you had a very large and positive effect on my life and career.  Starting with the complexity theory summer school at the Institute for Advanced Study in 2000, which was the first time we met and also the first time I really experienced the glories of complexity at full blast.  And then continuing at Berkeley, TA’ing your algorithms class, which you had to cancel on 9/11 (although students still somehow showed up for office hours lugging their CLRS books…), and dealing with that student who obviously cheated on the midterm although I had stupidly given back to her the evidence that would prove it.

And then your graduate complexity course, where I was very proud to get 100% on your exam, having handwritten it on a train while everyone else used LaTeX (which, embarrassingly, I was still learning).  I was a bit less proud to present the Razborov-Rudich paper to the class, and to get questions from you that proved that I understood it less thoroughly than I thought.  I emerged from your course far better prepared to do complexity theory than when I entered it.

Later I took your cryptography course, where I came to you afterwards one day to point out that with a quantum computer, you could pull out big Fourier coefficients without all the bother of the Goldreich-Levin theorem.  And you said sure, but then you would need a quantum computer.  Over 20 years later, Goldreich and Levin (and you?) can say with satisfaction that we still don’t have that scalable quantum computer … but we’re much much closer, I swear!

I still feel bad about the theory lunch talk I gave in 2003, on my complexity-theoretic version of Aumann’s agreement theorem, where I used you and Umesh as characters instead of Alice and Bob, and which then led to unintended references to “Luca’s posterior.”

I also feel bad about delaying so long the completion of my PhD thesis, until well after I’d started my postdoc in Princeton, so that my former officemate needed to meet you on a street corner in San Francisco to sign the signature page the night before the deadline.

But then a few years later, when Avi and I did the algebrization paper, the fact that you seemed to like it mattered more to me than just about anything else.

Thank you for the excellent dinner when I met you some years ago in Rome.  Thank you for the Trevisan-Tulsiani-Vadhan paper, which answered a question we had about BosonSampling (and you probably didn’t even know you were doing quantum computing when you wrote that paper!).  Thank you for your blog.  Thank you for everything you did for me.

I always enjoyed your dry humor, much of which might sadly be lost to time, unless others wrote it down or it’s on YouTube or something. Two examples spring to my mind across the decades:

“From my previous lecture, you may have gotten the impression that everything in derandomization is due to Nisan and Wigderson, but this is not the case: Avi has been working with other people as well.”After I’d explained that I’d be spending a semester in Jerusalem to work with Avi Wigderson, despite (at that time) knowing only the most rudimentary Hebrew, such as how to say “please” and “excuse me”: “you mean there are words in Hebrew for ‘please’ and ‘excuse me’?”

Speaking of which, my current trip to Israel has given me many opportunities to reflect on mortality — for all the obvious war-related reasons of course, but also because while we were here, we unexpectedly had to attend two shivas of people in our social circle who died during our trip, one of them from cancer.  And we learned about a close friend whose stepson has a brain tumor and might or might not make it.  Cancer is a bitch.

Anyway, there’s much more I could write, but I imagine you’re getting flooded with emails right now from all the people whose lives you’ve touched, so I won’t take up more of your time.  You’ve made a real difference to the world, to theoretical computer science, and to your friends and colleagues, one that many people would envy.

Best,
Scott