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.

Last night a colleague sent me a gracious message, wishing for the safe return of the hostages and expressing disgust over the antisemites in my comment section. I wanted to share my reply.

---

You have no idea how much this means to me.

I’ve just been shaking with anger after an exchange with the latest antisemite to email me. After I asked her whether she really wished for my family and friends in Israel to be murdered, she said that if I “read a fucking book that’s not about computers,” I would understand that “violence is the language of the oppressed.”

The experience of the last few weeks has radicalized me like nothing else in life. I’m not the same person as I was in September. My priorities are not the same. 48% of Americans aged 18-24 now say that they sympathize with Hamas more than Israel. Not with the Palestinian people, with Hamas. That’s nearly half of the next generation of my own country that might want me and my loved ones to be slaughtered.

I feel like the last thread connecting me to my previous life are the people like you, who write to me with kindness and understanding, and who make me think: there are Gentiles who would’ve hidden me under the floorboards when the SS showed up.

Be well.
—Scott

Another Update (Oct. 27): At Boaz Barak’s Windows on Theory blog, you can now find a petition signed by 63 prize-winning mathematicians and computer scientists—one guess which one is alphabetically first—asking that the kidnapped Israeli children be returned home. I feel confident that the pleas of Fields Medalists and Turing Award laureates will be what finally makes Hamas see the light.

---

Update: Every time another antisemite writes to me to excuse, justify, or celebrate Hamas’s orgy of murder and kidnapping, I make another donation to the Jewish Federations of North America to help Israeli terror victims, listing the antisemite’s name or alias in the “in honor of” field. By request, I’m sharing the link in case anyone else is also interested to donate.

---

Aharon Brodutch is a quantum computing researcher who I’ve known for nearly a decade. He’s worked at the Institute for Quantum Computing in Waterloo, the University of Toronto, his own startup company, and most recently IonQ. He’s thought about quantum discord, the one-clean-qubit model, weak measurements, and other topics that have long been of interest on this blog. He’s also on the paper giving an adaptive attack against Wiesner’s quantum money scheme—an application of the Elitzur-Vaidman bomb tester so simple and beautiful that I teach it in my undergrad Intro to Quantum Information Science class.

Yesterday I learned that Aharon’s sister-in-law Hagar, his niece Ofri, and his two nephews Yuval and Uriah were kidnapped by Hamas. Like Jews around the world, I’ve spent the last two weeks endlessly learning the names, faces, and life stories of hundreds of Israeli civilians who were murdered or kidnapped—and yet this news, directly affecting a colleague of mine, still managed to hit me in the gut.

My sister in law Hagar, my niece Ofri and my two nephews Yuval and Uriah were kidnapped into Gaza. We want them home where they belong. #BringThemHowNow pic.twitter.com/pMDZquu0ml

— Aharon Brodutch (@ABrodutch) October 19, 2023

I’m gratified that much of the world shares my revulsion at Hamas’s pogrom—the worst violence against Jews since the Holocaust—and joins me in wishing for the safe return of the 200 hostages as well as the destruction of Hamas, and its replacement by a governing authority that actually cares about the welfare of the Palestinian people. I’m glad that even many who call themselves “anti-Israel” or “anti-Zionist” have the basic human decency to be disgusted by Hamas. Some of the most touching messages of love and support that I got came from my Iranian friends.

All the same, for a whole week, my inbox and my blog moderation queue have been filling up with missives from people who profess to be thrilled, delighted, exhilirated by what Hamas did. They tell me that the young people at the Nova music festival had it coming, and that they hope Hamas burns the settler-colonialist Zionist entity to the ground. While some of these people praise Adolf Hitler, others parrot social-justice slogans. One of these lovely correspondents claimed that virtually all of his academic colleagues in history and social science share his attitudes, and said I had no right to lecture him as a mere computer scientist.

Meanwhile, as quantum computing founder David Deutsch has documented on his Twitter, in cities and university campuses around the world, posters with the names and faces of the children kidnapped by Hamas—just the names and faces of the kidnapped children (!)—are being torn down by anti-Israel activists. The cognitive dissonance involved in such an act is astounding, but also deeply informative about the millennia-old forces at work here.

One way I’ve been coping with this is, every time a Jew-hater emails me, I make another donation to help the victims in Israel, specifying that my donation is being made in the Jew-hater’s name. But another way to cope is simply to use this blog to make what’s at stake visceral and explicit to my readers. I got in touch with Aharon, and he asked me to share the guest post below, written by his brother Avihai. I said it was the least I could do. –Scott Aaronson

---

Guest Post by Avihai Brodutch

My name is Avihai Brodutch. My wife Hagar, along with our three children Ofri, Yuval, and Uriah, are being held hostage by Hamas. I want to share this message with people around the world: Children should never be involved in war. My wife and family should not be held hostage and they need to be released immediately.

Here’s my story:

I am an Israeli from Kfar Aza. My wife and I chose to build our home close to the border with Gaza, hoping for peace and relying on the Israeli government to protect our children. It was a beautiful home. Hagar, the love of my life, spent her entire life in Kibbutz Gvulot near the border. Our daughter Ofri, who is 10 years old, is an amazing, fun-loving girl who brings joy to everyone around her. Our son Yuval, 8, is smart, kind, and loving. And our youngest, Uriah, is the cutest little rascal. He is four and a half years old.  All four of them are in the hands of Hamas, and I hope they are at least together.

On October 7th, our family’s life was shattered by a brutal attack. Hamas terrorists infiltrated Kfar Aza early in the morning while I was away from home. Security alerts are common in the kibbutz, and we all thought this one was no different until Hagar heard a knock on the door and saw the neighbor’s 4-year-old girl, Avigail, covered in blood. Both her parents had been murdered, and Hagar took Avigail in. She locked the door, and they all hid in the house. Soon, the entire kibbutz was filled with the sounds of bullets and bombs.

I maintained contact with Hagar, who informed me that she had secured the door and was hiding with the children. We communicated quietly through text messages until she messaged, “they are coming in.” At that point, we lost communication, and I was convinced that I had lost my wife and three children. I do not want to describe the images that raced through my mind. A day later, I received word that a neighbor had witnessed them being captured and taken to Gaza. My family was alive, and this was the happiest news I’ve ever received. However, I knew they were far from being safe.

I am asking all the governments in the world, do the right thing and help bring my family back to safety. This is not controversial, it is obvious to every human, the first priority should be bringing the families back home. 

Update (Oct. 11): While this post celebrated Harvard’s Boaz Barak, and his successful effort to shame his into disapproving of the murder of innocents, I missed Boaz’s best tweet about this. There, Boaz points out that there might be a way to get Western leftists on board with basic humanity on this issue. Namely: we simply need to unearth video proof that, at some point before beheading their Jewish victims in front of their families, burning them alive, and/or parading their mutilated bodies through the streets, at some point Hamas also misgendered them.

---

The purpose of this post is to salute a longtime friend-of-the-blog for a recent display of moral courage.

---

Boaz Barak is one of the most creative complexity theorists and cryptographers in the world, Gordon McKay Professor of Computer Science at Harvard, and—I’m happy to report—soon (like me) to go on leave to work in OpenAI’s safety group. He’s a longtime friend-of-the-blog (having, for example, collaborated with me on the Five Worlds of AI post and Alarming trend in K-12 math education post), not to mention a longtime friend of me personally.

Boaz has always been well to my left politically. Secular, Israeli-born, and a protege of the … err, post-Zionist radical (?) Oded Goldreich, I can assure you that Boaz has never been quiet in his criticisms of Bibi’s emerging settler-theocracy.

This weekend, though, a thousand Israelis were murdered, kidnapped, and raped—children, babies, parents using their bodies to shield their kids, Holocaust survivors, young people at a music festival. It’s already entered history as the worst butchery of Jews since the Holocaust.

In response, 35 Harvard student organizations quickly issued a letter blaming Israel “entirely” for the pogrom, and expressing zero regrets of any kind about it—except for the likelihood of “colonial retaliation,” against which the letter urged a “firm stand.” Harvard President Claudine Gay, outspoken on countless other issues, was silent in response to the students’ effective endorsement of the Final Solution. So Boaz wrote an open letter to President Gay, a variant of which has now been signed by a hundred Harvard faculty. The letter reads, in part:

Every innocent death is a tragedy. Yet, this should not mislead us to create false equivalencies between the actions leading to this loss. Hamas planned and executed the murder and kidnapping of civilians, particularly women, children, and the elderly, with no military or other specific objective. This meets the definition of a war crime.  The Israeli security forces were engaging in self-defense against this attack while dealing with numerous hostage situations and a barrage of thousands of rockets hidden deliberately in dense urban settings.

The leaders of the major democratic countries united in saying that “the terrorist actions of Hamas have no justification, no legitimacy, and must be universally condemned” and that Israel should be supported “in its efforts to defend itself and its people against such atrocities.“ In contrast, while terrorists were still killing Israelis in their homes,  35 Harvard student organizations wrote that they hold “the Israeli regime entirely responsible for all unfolding violence,” with not a single word denouncing the horrific acts by Hamas. In the context of the unfolding events, this statement can be seen as nothing less than condoning the mass murder of civilians based only on their nationality. We’ve heard reports of even worse instances, with Harvard students celebrating the “victory” or “resistance” on social media.

As a University aimed at educating future leaders, this could have been a teaching moment and an opportunity to remind our students that beyond our political debates, some acts such as war crimes are simply wrong. However, the statement by Harvard’s administration fell short of this goal. While justly denouncing Hamas, it still contributed to the false equivalency between attacks on noncombatants and self-defense against those atrocities. Furthermore, the statement failed to condemn the justifications for violence that come from our own campus, nor to make it clear to the world that the statement endorsed by these organizations does not represent the values of the Harvard community.  How can Jewish and Israeli students feel safe on a campus in which it is considered acceptable to justify and even celebrate the deaths of Jewish children and families?

Boaz’s letter, and related comments by former Harvard President Larry Summers, seem to have finally spurred President Gay into dissociating the Harvard administration from the students’ letter.

---

When I get depressed about the state of the world—as I have a lot the past few days—it helps to remember the existence of such friends, not only in the world but in my little corner of it.

My wife’s family is OK; thanks very much for asking. But yes, missiles are landing and sirens are going off in Tel Aviv, and people there regularly have to use their buildings’ bomb shelters.

Of course, the main developments are further south, where at least seven hundred Israelis were murdered or kidnapped and thousands were wounded, in what’s being called “Israel’s 9/11” (ironically, I remember 9/11 itself being called America’s Israel experience). Some back-of-the-envelopes: this weekend, the number of Jews murdered for being Jews was about 12% of the number murdered per day in Auschwitz when it operated at max capacity, and nearly as many as were killed in the entire Six-Day War (most of whom were soldiers). It was also about ten 9/11’s, if scaled by the Israeli vs. US population.

As for why this war started, Hamas itself cited, not any desire to improve the miserable conditions of the people under its charge, but a few ultra-Orthodox Jews praying on the Temple Mount — a theological rationale.

This is either the worst intelligence and operational failure in Israeli history or the second-worst, after the Yom Kippur War. It’s impossible not to ask whether the total political dysfunction gripping Israel played a central role, whether Netanyahu’s ministers were much more interested in protecting West Bank settlers than in protecting communities near Gaza, and whether Hamas and Iran knowingly capitalized on all this. But there will be investigations afterward.

For now, both sides of Israel’s internal conflict — the secular modernists and the religious nationalist Bibi-ists — are completely united behind the goal of winning this unasked-for war, with the support of the world’s Jewish diaspora and reasonable people and nations, because what alternative is there?

Added: This Quillette article is good for the historical context that many Western intellectuals refuse to understand. Namely: for everything the Israeli government has done wrong, in Hamas it faces an enemy that descends directly from the Grand Mufti’s fusion of Nazism and Islamism in the 1930s and 1940s, and whose goal since its founding has been explicitly genocidal toward all Jews everywhere on earth—as we saw in the worst massacre of Jews since the Holocaust that it carried out this weekend.

---

Update: This is really, really not thematically appropriate to this post, but … an interview with me, entitled Scott Aaronson Disentangles Quantum Hype, is now available on Craig Smith’s “Eye on AI” podcast. Give it a listen if you’re interested.

1. Tomorrow at 1:30pm US Central time, I’ll be doing an online Q&A with Collective[i] Forecast about quantum computing (probably there will also be questions about AI safety). It’s open to all. Hope to see some of you there!
   
2. Toby Cubitt of University College London is visiting UT Austin. We’ve been discussing the question: can you produce a QMA witness state using a closed timelike curve? Since QMA⊆PSPACE, and since Fortnow, Watrous, and I proved that closed timelike curves (or anyway, Deutsch’s model of them) let you solve PSPACE problems, clearly a closed timelike curve lets you solve QMA decision problems, but that’s different from producing the actual witness state as the fixed-point of a polynomial-time superoperator. Toby has a neat recent result, which has as a corollary that you can produce the ground state of a local Hamiltonian using a CTC, if you have as auxiliary information the ground state energy as well as (a lower bound on) the spectral gap. But you do seem to need that extra information.
   
   Yesterday I realized there’s also a simpler construction: namely, take an n-qubit state from the CTC, and check whether it’s a valid QMA witness, having used Marriott-Watrous amplification to push the probability of error down to (say) exp(-n²). If the witness is valid, then send it back in time unmodified; otherwise replace it by the maximally mixed state. If valid witnesses exist, then you can check that this sets up a Markov chain whose stationary distribution is almost entirely concentrated on such witnesses. (If no valid witnesses exist, then the stationary distribution is just the maximally mixed state, or exponentially close to it.) One drawback of this construction is that it can only produce a Marriott-Watrous state, rather than the “original” QMA witness state.
   
   Is there a third approach, which overcomes the disadvantages of both mine and Toby’s? I’ll leave that question to my readers!
   
3. On the theme of QMA plus weird physics, a wonderful question emerged from a recent group meeting: namely, what’s the power of QMA if we let the verifier make multiple non-collapsing measurements of the same state, as in the “PDQP” model defined by myself, Bouland, Fitzsimons, and Lee? I conjecture that this enhanced QMA goes all the way up to NEXP (Nondeterministic Exponential-Time), by a construction related to the one I used to show that PDQP/qpoly = ALL (i.e., non-collapsing measurements combined with quantum advice lets you decide literally all languages), and that also uses the PCP Theorem. I even have some candidate constructions, though I haven’t yet proven their soundness.
   
   In the past, I would’ve spent more time on such a problem before sharing it. But after giving some students a first crack, I now … just want to know the answer? Inspecting my feelings in my second year of leave at OpenAI, I realized that I still care enormously about quantum complexity theory, but only about getting answers to the questions, barely at all anymore about getting credit for them. Admittedly, it took me 25 years to reach this state of not caring.

1. Ben Brubaker wrote a long piece for Quanta magazine about meta-complexity. The first three-quarters are a giant refresher on the story of computability and complexity theory in the 20th century—including Turing, Gödel, Shannon, Cook, Karp, Levin, Baker-Gill-Solovay, Sipser, Razborov, Rudich, and more. But then the last quarter gets into actually new (well, within the last couple years) developments, including the NP-completeness of “Partial-MCSP” and other progress on the Minimum Circuit Size Problem, and progress toward basing cryptography on the sole assumption P≠NP, and ruling out Impagliazzo’s “Heuristica” and “Pessiland” worlds. I’m quoted (and helped proofread the piece) despite playing no role in the new developments. Worth a read if you don’t already know this stuff.
   
2. Duane Rich created a Part II of his YouTube video series on the Busy Beaver function. It features some of the core ideas from my Busy Beaver survey, clearly narrated and beautifully animated. If reading my survey is too much for you, now you can just watch the movie!
   
3. Aznaur Midov recorded a podcast with me about quantum computing and AI—just in case you haven’t got enough of either of those lately.
   
4. Oded Regev put an exciting paper on the arXiv, showing how to factor an n-digit integer using quantum circuits of size ~O(n^3/2) (multiple such circuits, whose results are combined classically), assuming a smoothness conjecture from number theory. This compares to ~O(n²) for Shor’s algorithm. Regev’s algorithm uses classical algorithms for lattice problems, thereby connecting that subject to quantum factoring. This might or might not bring nearer in time the day when we can break (say) 2048-bit RSA keys using a quantum computer—that mostly depends, apparently, on whether Regev’s algorithm can also be made highly efficient in its use of qubits.
   
5. A team from IBM, consisting of Sergey Bravyi, Andrew Cross, Jay Gambetta, Dmitri Maslov, Ted Yoder, and my former student Patrick Rall, put another exciting paper on the arXiv, which reports an apparent breakthrough in quantum error-correction—building a quantum memory based on LDPC (Low Density Parity Check) codes rather than the Kitaev surface code, and which (they say) with an 0.1% physical error rate, can preserve 12 logical qubits for ten million syndrome cycles using 288 physical qubits, rather than more than 4000 physical qubits with the surface code. Anyone who understands in more detail is welcome to comment!
   
6. Boaz Barak wrote a blog post about the history of the atomic bomb, and possible lessons for AI development today. I’d been planning to write a blog post about the history of the atomic bomb and possible lessons for AI development today. Maybe I’ll still write that blog post.
   
7. Last week I attended the excellent Berkeley Simons Workshop on Large Language Models and Transformers, hosted by my former adviser Umesh Vazirani. While there, I gave a talk on watermarking of LLMs, which you can watch on YouTube (see also here for the PowerPoint slides). Shtetl-Optimized readers might also enjoy the talk by OpenAI cofounder Ilya Sutskever, An Observation on Generalization, as well as many other talks on all aspects of LLMs, from theoretical to empirical to philosophical to legal.
   
8. Right now I’m excited to be at Crypto’2023 in Santa Barbara, learning a lot about post-quantum crypto and more, while dodging both earthquakes and hurricanes. On Wednesday, I’ll give an invited plenary talk about “Neurocryptography”: my vision for what cryptography can contribute to AI safety, including via watermarking and backdoors. Who better to enunciate such a vision than someone who’s neither a cryptographer nor an AI person? If you’re at Crypto and see me, feel free to come say hi.