Shtetl-Optimized

Yet Another Update (Dec. 5): For those who still haven’t had enough of me, check me out on Curt Jaimungal’s Theories of Everything Podcast, talking about … err, computational complexity, the halting problem, the time hierarchy theorem, free will, Newcomb’s Paradox, the no-cloning theorem, interpretations of quantum mechanics, Wolfram, Penrose, AI, superdeterminism, consciousness, integrated information theory, and whatever the hell else Curt asks me about. I strongly recommend watching the video at 2x speed to smooth over my verbal infelicities.

In answer to a criticism I’ve received: I agree that it would’ve been better for me, in this podcast, to describe Wolfram’s “computational irreducibility” as simply “the phenomenon where you can’t predict a computation faster than by running it,” rather than also describing it as a “discrete analog of chaos / sensitive dependence on initial conditions.” (The two generally co-occur in the systems Wolfram talks about, but are not identical.)

On the other hand: no, I do not recognize that Wolfram deserves credit for giving a new name (“computational irreducibility”) to a thing that was already well-understood in the relevant fields.  This is particularly true given that

(1) the earlier understanding of the halting problem and the time hierarchy theorem was rigorous, giving us clear criteria for proving when computations can be sped up and when they can’t be, and

(2) Wolfram replaced it with handwaving (“well, I can’t see how this process could be predicted faster than by running it, so let’s assume that it can’t be”).

In other words, the earlier understanding was not only decades before Wolfram, it was superior.

It would be as if I announced my new “Principle of Spacetime Being Like A Floppy Trampoline That’s Bent By Gravity,” and then demanded credit because even though Einstein anticipated some aspects of my principle with his complicated and confusing equations, my version was easier for the layperson to intuitively understand.

I’ll reopen the comments on this post, but only for comments on my Theories of Everything podcast.

---

Another Update (Dec. 1): Quanta Magazine now has a 20-minute explainer video on Boolean circuits, Turing machines, and the P versus NP problem, featuring yours truly. If you already know these topics, you’re unlikely to learn anything new, but if you don’t know them, I found this to be a beautifully produced introduction with top-notch visuals. Better yet—and unusually for this sort of production—everything I saw looked entirely accurate, except that (1) the video never explains the difference between Turing machines and circuits (i.e., between uniform and non-uniform computation), and (2) the video also never clarifies where the rough identities “polynomial = efficient” and “exponential = inefficient” hold or fail to hold.

---

For the many friends who’ve asked me to comment on the OpenAI drama: while there are many things I can’t say in public, I can say I feel relieved and happy that OpenAI still exists. This is simply because, when I think of what a world-leading AI effort could look like, many of the plausible alternatives strike me as much worse than OpenAI, a company full of thoughtful, earnest people who are at least asking the right questions about the ethics of their creations, and who—the real proof that they’re my kind of people—are racked with self-doubts (as the world has now spectacularly witnessed). Maybe I’ll write more about the ethics of self-doubt in a future post.

For now, the narrative that I see endlessly repeated in the press is that last week’s events represented a resounding victory for the “capitalists” and “businesspeople” and “accelerationists” over the “effective altruists” and “safetyists” and “AI doomers,” or even that the latter are now utterly discredited, raw egg dripping from their faces. I see two overwhelming problems with that narrative. The first problem is that the old board never actually said that it was firing Sam Altman for reasons of AI safety—e.g., that he was moving too quickly to release models that might endanger humanity. If the board had said anything like that, and if it had laid out a case, I feel sure the whole subsequent conversation would’ve looked different—at the very least, the conversation among OpenAI’s employees, which proved decisive to the outcome. The second problem with the capitalists vs. doomers narrative is that Sam Altman and Greg Brockman and the new board members are also big believers in AI safety, and conceivably even “doomers” by the standards of most of the world. Yes, there are differences between their views and those of Ilya Sutskever and Adam D’Angelo and Helen Toner and Tasha McCauley (as, for that matter, there are differences within each group), but you have to drill deeper to articulate those differences.

In short, it seems to me that we never actually got a clean test of the question that most AI safetyists are obsessed with: namely, whether or not OpenAI (or any other similarly constituted organization) has, or could be expected to have, a working “off switch”—whether, for example, it could actually close itself down, competition and profits be damned, if enough of its leaders or employees became convinced that the fate of humanity depended on its doing so. I don’t know the answer to that question, but what I do know is that you don’t know either! If there’s to be a decisive test, then it remains for the future. In the meantime, I find it far from obvious what will be the long-term effect of last week’s upheavals on AI safety or the development of AI more generally. For godsakes, I couldn’t even predict what was going to happen from hour to hour, let alone the aftershocks years from now.

---

Since I wrote a month ago about my quantum computing colleague Aharon Brodutch, whose niece, nephews, and sister-in-law were kidnapped by Hamas, I should share my joy and relief that the Brodutch family was released today as part of the hostage deal. While it played approximately zero role in the release, I feel honored to have been able to host a Shtetl-Optimized guest post by Aharon’s brother Avihai. Meanwhile, over 180 hostages remain in Gaza. Like much of the world, I fervently hope for a ceasefire—so long as it includes the release of all hostages and the end of Hamas’s ability to repeat the Oct. 7 pogrom.

---

Greta Thunberg is now chanting to “crush Zionism” — ie, taking time away from saving civilization to ensure that half the world’s remaining Jews will be either dead or stateless in the civilization she saves. Those of us who once admired Greta, and experience her new turn as a stab to the gut, might be tempted to drive SUVs, fly business class, and fire up wood-burning stoves just to spite her and everyone on earth who thinks as she does.

The impulse should be resisted. A much better response would be to redouble our efforts to solve the climate crisis via nuclear power, carbon capture and sequestration, geoengineering, cap-and-trade, and other effective methods that violate Greta’s scruples and for which she and her friends will receive and deserve no credit.

(On Facebook, a friend replied that an even better response would be to “refuse to let people that we don’t like influence our actions, and instead pursue the best course of action as if they didn’t exist at all.” My reply was simply that I need a response that I can actually implement!)

No, I don’t know what happened with Sam Altman, beyond what’s being reported all over the world’s press, which I’ve been reading along with everyone else. Ilya Sutskever does know, and I talk to Ilya nearly every week. But I know Ilya well enough to know that whatever he’d tell me about this, he’d also tell the world. It feels weird to be so close to the biggest news story on the planet, and yet at the same time so far from it. My current contract with OpenAI is set to expire this summer. Until then, and afterwards, I remain just as interested in figuring out what theoretical computer science can contribute to AI safety as I was yesterday morning.

My friend, theoretical computer science colleague, and now OpenAI colleague Boaz Barak has coauthored a paper giving a general class to attack against watermarking methods for large language models—100% consistent with the kinds of attacks we already knew about and were resigned to, but still good to spell out at a formal level. I hope to write more about it in the future.

Here’s a recent interview with me in Politico, touching on quantum computing, AI, and more.

And if that’s not enough of me, here’s a recent podcast that I did with Theo Jaffee, touching on quantum computing, P vs. NP, AI alignment, David Deutsch, and Twitter.

Whatever feelings anyone has about it, the new University of Austin (not to be confused with the University of Texas at Austin, where I work) is officially launching. And they’re hiring! People who are interested in STEM positions there should contact David Ruth.

I forgot to link to it when it came out more than a month ago—a lot has happened in the meantime!—but Dalzell et al. put up a phenomenal 337-page survey of quantum algorithms, focusing relentlessly on the crucial question of whether there’s actually an end-to-end speedup over the best known classical algorithm for each given task. In countless situations where I would just scream “no, the hypesters are lying to you, this is BS,” Dalzell et al. take dozens of polite, careful, and highly technical pages to spell out why.

Besides AI intrigue, this past week might be remembered for a major breakthrough in classical complexity theory, in solving arbitrary compression problems via a nonuniform algorithm (i.e., a family of Boolean circuits) that takes only 2^4n/5 time, rather than the 2ⁿ time that would be needed for brute force. See this paper by Hirahara, Ilango, and Williams, and as well this independent one by Mazor and Pass.

I’ve been drowning in both quantum-computing-related and AI-related talks, interviews, podcasts, panels, and so on. These activities have all but taken over my days, leaving virtually no time for the actual research (especially once one factors in time for family, and time for getting depressed on social media). I’ve let things reach this point partly because I really do love talking about things that interest me, but partly also because I never learned how to say no. I have no choice but to cut back.

So, the purpose of this post is for me to link people to it whenever I get a new request. From now on, I agree only under the following conditions:

1. For travel: you reimburse all travel costs. I don’t have to go through a lengthy process for reimbursements, but just forward you my receipts. There’s not a time limit on doing so.
2. You don’t require me to upload my slides in advance, or provide readings or other “extra” materials. (Title and abstract a week or two before the talk are reasonable.)
3. You don’t require me to schedule a “practice session” or “orientation session” before the main event.
4. For podcasts and virtual talks: you don’t require me to set up any special equipment (including headphones or special cameras), or install any special software.
5. If you’re a for-profit company: you compensate me for the time.
6. For podcasts and virtual talks: unless specified otherwise, I am in Austin, TX, in US Central time zone. You email me a reminder the day before with the time in US Central, and the link. Otherwise I won’t be held responsible in the likely event that we get it wrong.

So, Sam Bankman-Fried has been found guilty on all counts, after the jury deliberated for just a few hours. His former inner circle all pointed fingers at him, in exchange for immunity or reduced sentences, and their testimony doomed him. The most dramatic was the testimony of Caroline Ellison, the CEO of Alameda Research (to which FTX gave customer deposits) and SBF’s sometime-girlfriend. The testimony of Adam Yedidia, my former MIT student, who Shtetl-Optimized readers might remember for our paper proving the value of the 8000th Busy Beaver number independent of the axioms of set theory, also played a significant role. (According to news reports, Adam testified about confronting SBF during a tennis match over $8 billion in missing customer deposits.)

Just before the trial, I read Michael Lewis’s much-discussed book about what happened, Going Infinite. In the press, Lewis has generally been savaged for getting too close to SBF and for painting too sympathetic a portrait of him. The central problem, many reviewers explained, is that Lewis started working on the book six months before the collapse of FTX—when it still seemed to nearly everyone, including Lewis, that SBF was a hero rather than villain. Thus, Going Infinite reads like tale of triumph that unexpectedly veers at the end into tragedy, rather than the book Lewis obviously should’ve written, a tragedy from the start.

Me? I thought Going Infinite was great. And it was great partly because of, rather than in spite of, Lewis not knowing how the story would turn out when he entered it. The resulting document makes a compelling case for the radical contingency and uncertainty of the world—appropriate given that the subject, SBF, differed from those around him in large part by seeing everything probabilistically all the time (infamously, including ethics).

In other contexts, serious commentators love to warn against writing “Whig history,” the kind where knowledge of the outcome colors the whole. With the SBF saga, though, there seems to be a selective amnesia, where all the respectable people now always knew that FTX—and indeed, cryptocurrency, utilitarianism, and Effective Altruism in their entirety—were all giant scams from the beginning. Even if they took no actions based on that knowledge. Even if the top crypto traders and investors, who could’ve rescued or made fortunes by figuring out that FTX was on the verge of collapse, didn’t. Even if, when people were rightly suspicious about FTX, it still mostly wasn’t for the right reasons.

Going Infinite takes the radical view that, what insiders and financial experts didn’t know at the time, the narrative mostly shouldn’t know either. It should show things the way they seemed then, so that readers can honestly ponder the question: faced with this evidence, when would I have figured it out?

---

Even if Michael Lewis is by far the most sympathetic person to have written about SBF post-collapse, he still doesn’t defend him, not really. He paints a picture of someone who could totally, absolutely have committed the crimes for which he’s now been duly convicted. But—and this was the central revelation for me—Lewis also makes it clear that SBF didn’t have to.

With only “minor” changes, that is, SBF could still be running a multibillion-dollar cryptocurrency empire to this day, without lying, stealing, or fraud, and without the whole thing being especially vulnerable to collapse. He could have donated his billions to pandemic prevention and AI risk and stopping Trump. He conceivably even could’ve done more good, in one or more of those ways, than anyone else in the world was doing. He didn’t, but he came “close.” The tragedy is all the greater, some people might even say that SBF’s culpability (or the rage we should feel at him, or at fate) is all the greater, because of how close he came.

I’m not a believer in historical determinism. I’ve argued before on this blog that if Yitzhak Rabin hadn’t been killed—if he’d walked down the staircase a little differently, if he’d survived the gunshot—there would likely now be peace between Israel and Palestine. For that matter: if Hitler hadn’t been born, if he’d been accepted to art school, if he’d been shot while running between trenches in WWI, there would probably have been no WWII, and with near-certainty no Holocaust. Likewise, if not for certain contingent political developments of the 1970s (especially, the turn away from nuclear power), the world wouldn’t now face the climate crisis.

Maybe there’s an arc of the universe that bends toward horribleness. Or maybe someone has to occupy the freakishly horrible branches of the wavefunction, and that someone happens to be you and me. Or maybe the freakishly improbable good (for example, the availability of Winston Churchill and Alan Turing to win WWII) actually balances out the freakishly improbable bad in the celestial accounting, if only we could examine the books. Whatever the case, again and again civilization’s worst catastrophes were at least proximately caused by seemingly minor events that could have turned out differently.

But what’s the argument that FTX, Alameda, and SBF’s planet-sized philanthropic mission “could have” succeeded? It rests on three planks:

First, FTX was actually a profitable business till the end. It brought in hundreds of millions per year—meaning fees, not speculative investments—and could’ve continued doing so more-or-less indefinitely. That’s why even FTX’s executives were shocked when FTX became unable to honor customer withdrawals: FTX made plenty of money, so where the hell did it all go?

Second: we now have the answer to that mystery. John Ray, the grizzled CEO who managed FTX’s bankruptcy, has successfully recovered more than 90% of the customer funds that went missing in 2022! The recovery was complicated, enormously, by Ray’s refusal to accept help from former FTX executives, but ultimately the money was still there, stashed under the virtual equivalent of random sofa cushions.

Yes, the funds had been illegally stolen from FTX customer deposits—according to trial testimony, at SBF’s personal direction. Yes, the funds had then been invested in thousands of places—incredibly, with no one person or spreadsheet or anything really keeping track. Yes, in the crucial week, FTX was unable to locate the funds in time to cover customer withdrawals. But holy crap, the rockets’ red glare, the bombs bursting in air—the money was still there! Which means: if FTX had just had better accounting (!), the entire collapse might not have happened. This is a crucial part of the story that’s gotten lost, which is why I’m calling so much attention to it now. It’s a part that I imagine should be taught in accounting courses from now till the end of time. (“This double-entry bookkeeping might seem unsexy, but someday it could mean the difference between you remaining the most sought-after wunderkind-philanthropist in the world, and you spending the rest of your life in prison…”)

Third, SBF really was a committed utilitarian, as he apparently remains today. As a small example, he became a vegan after my former student Adam Yedidia argued him into it, even though giving up chicken was extremely hard for him. None of it was an act. It was not a cynical front for crime, or for the desire to live in luxury (something SBF really, truly seems not to have cared about, although he indulged those around him who did). When I blogged about SBF last fall, I mused that I’d wished I’d met him back when he was an undergrad at MIT and I was a professor there, so that I could’ve tried to convince him to be more risk-averse: for example, to treat utility as logarithmic rather than linear in money. To my surprise, I got bitterly attacked for writing that: supposedly, by blaming a “merely technical” failure, I was excusing SBF’s far more important moral failure.

But reading Lewis confirmed for me that it really was all part of the same package. (See also here for Sarah Constantin’s careful explanation of SBF’s failure to understand the rationale for the Kelly betting criterion, and how many of his later errors were downstream of that.) Not once but over and over, SBF considers hypotheticals of the form “if this coin lands heads then the earth gets multiplied by three, while if it lands tails then the earth gets destroyed”—and always, every time, he chooses to flip the coin. SBF was so committed to double-or-nothing that he’d take what he saw as a positive-expected-utility gamble even when his customers’ savings were on the line, even when all the future good he could do for the planet as well as the reputation of Effective Altruism were on the line, even when his own life and freedom were on the line.

On the one hand, you have to give that level of devotion to a principle its grudging due. On the other hand, if “the Gambler’s Ruin fallacy is not a fallacy” is so central to someone’s worldview, then how shocked should we be when he ends up … well, in Gambler’s Ruin?

The relevance is that, if SBF’s success and downfall alike came from truly believing what he said, then I’m plausibly correct that this whole story would’ve played out differently, had he believed something slightly different. And given the role of serendipitous conversations in SBF’s life (e.g., one meeting with William MacAskill making him an Effective Altruist, one conversation with Adam Yedidia making him a vegan), I find it plausible that a single conversation might’ve set him on the path to a less brittle, more fault-tolerant utilitarianism.

---

Going Infinite shows signs of being finished in a hurry, in time for the trial. Sometimes big parts of the story seem skipped over without comment; we land without warning in a later part and have to reorient ourselves. There’s almost nothing about the apparent rampant stimulant use at FTX and the role it might have played, nor does Lewis ever directly address the truth or falsehood of the central criminal charge against SBF (namely, that he ordered his subordinates to move customer deposits from FTX’s control to Alameda’s). Rather, the book has the feeling of a series of magazine articles, as Lewis alights on one interesting topic after the next: the betting games that Jane Street uses to pick interns (SBF discovered that he excelled at those games, unfortunately for him and for the world). The design process (such as it was) for FTX’s never-built Bahamian headquarters. The musings of FTX’s in-house psychotherapist, George Lerner. The constant struggles of SBF’s personal scheduler to locate SBF, get his attention, and predict where he might go next.

When it comes to explaining cryptocurrency, Lewis amusingly punts entirely, commenting that the reader has surely already read countless “blockchain 101” explainers that seemed to make sense at the time but didn’t really stick, and that in any case, SBF himself (by his own admission) barely understood crypto even as he started trading it by the billions.

Anyway, what vignettes we do get are so vividly written that they’ll clearly be a central part of the documentary record of this episode—as anyone who’d read any of Lewis’s previous books could’ve predicted.

And for anyone who accuses me or Lewis of excusing SBF: while I can’t speak for Lewis, I don’t even excuse myself. For the past 15 years, I should have paid more attention to cryptocurrency, to the incredible ease (in hindsight!) with which almost anyone could’ve ridden this speculative bubble in order to direct billions of dollars toward the salvation of the human race. If I wasn’t going to try it myself, then at least I should’ve paid attention to who else in my wide social circle was trying it. Who knows, maybe I could’ve discovered something about the extreme financial, moral, and legal risks those people were taking on, and then I could’ve screamed at them to turn the ship and avoid those risks. Instead, I spent the time proving quantum complexity theorems, and raising my kids, and teaching courses, and arguing with commenters on this blog. I was too selfish to enter the world of crypto billionaires.