Shtetl-Optimized

Scott’s foreword: Cynthia Dwork is Gordon McKay Professor of Computer Science at Harvard, and a pioneer in the fields of differential privacy and algorithmic fairness. On my recent travels to the SigmaWest science camp and then STOC, there was much talk about a recent Trump administration action that would ban not only differential privacy, but essentially all modern techniques for preserving privacy in large datasets, for example in the 2030 US Census. I realize that many of us have “outrage fatigue,” but this particular outrage hits extremely close to home for the CS theory community. So when Cynthia approached me at STOC to propose a guest post on the issue, of course I said yes. The post that she sent me, below, is cosigned by many other leaders in the field.

---

On June 4, 2026, the U.S. Secretary of Commerce issued a directive (DAO 216-26) relegating confidentiality protection in all Bureau of Economic Analysis (BEA) and U.S. Census Bureau publications to techniques dating back to the early 1970s, turning its back on over half a century of progress and protections for data subjects. Advances in confidentiality provision had enabled the Census Bureau to share increasing quantities of data at more granular detail. The order will result in less useful (or fewer available) statistics, weaker protection, or both. We write to illustrate the danger posed by the order and to mobilize the scientific community to speak out against it.

The acting force behind this order is political interest, not scientific merit. DAO 216-26 bypassed legally required administrative procedures. It fulfills a promise made by the architects of the Heritage Foundation’s Project 2025, and reflects both the rhetoric and misunderstandings of representatives of the Center for Renewing America (CRA), an organization founded by OMB Director Russell Vought. CRA’s explainer on the use of differential privacy in the 2020 Census is up-front about the stakes: “Even if the citizenship question is added to the Census, it will be impossible to ascertain the status of individuals so long as differential privacy is used.” But masking this sort of personal characteristics data is legally required by the Census Act (13 U.S. Code Section 9), which makes it a crime to “make any publication whereby the data furnished by any particular [individual] can be identified.” Confidentiality is also widely understood as critical to ensuring that people respond to the census. 

DAO-216-26 bans differential privacy and other modern (and not so modern) techniques. It restricts disclosure avoidance techniques to “coarsening,” which it describes as “reducing the level of detail or specificity of published statistics, such as through rounding, aggregating (grouping), and/or the use of ranges.” “Suppression” (“expressly redacting certain values”) may also be used, but only as a “last resort.” DAO-216-26 forbids “noise infusion”, described as “methods that involve modifying a dataset by adding random values, or noise.” 

Noise infusion was invented precisely to address the increasing demand for granular data in the face of confidentiality laws that forbid publishing reidentifiable data. Coarsening and suppression were satisfactory for most national, aggregate statistical series, like the Principal Federal Economic Indicators. However, these techniques failed when applied to business and demographic data at fine geographic or industrial detail. By forbidding noise infusion, the directive bans the disclosure avoidance techniques at the core of dozens of data releases over the last three decades. It bans input noise infusion, used in the Quarterly Workforce Indicators since 2002 and, until now, planned for the Bureau of Economic Analysis statistics [1].  It bans swapping, used for decennial census publications since 1990. It also bans differential privacy,  the best currently known approach for obtaining the most data utility for any given level of privacy. Differential privacy was used for sharing data on commuting patterns (OnTheMap) since 2008 and for publications based on the 2020 Census. Until the recent directive, differential privacy was planned for the 2030 Census too.  Many other products and procedures are implicated as well.

1.      Illustrations

DAO-216-26 is incompatible with the Census Bureau’s dual mandate to provide confidentiality and fitness for use. To illustrate this, we recall and expand on an example due to Nathan Goldschlag, inspired by the County Business Patterns (CBP) data, which provides statistics on business activity broken down by industry and geography. Goldschlag describes three scenarios, illustrating the tension between providing useful information and maintaining confidentiality of responses as required by the Census Act. 

·       “There is only one brewery in a small county. If the CBP published the exact count of brewery employees in that county, it would be disclosing the information of one business (how many workers it employs), a clear violation of the law.²

·        “There are two breweries in a small county, and the CBP again publishes the exact count of brewery employees. If I own one of those breweries, I could learn how many employees my competitor has, again violating the law.

·        “There are more than two breweries in a small county, but the CBP chooses not to publish the total number of brewery employees out of concern that it might compromise the privacy of the businesses. If I’m a prospective brewery owner, I may deem the project too risky to pursue without information about the market I’m entering.”

In Goldschlag’s example, coarsening makes the published statistics useless.  We now add a fourth scenario, showing that it also fails to maintain confidentiality.  To keep things simple, assume none of us owns any of the businesses in the new example. The County has two towns with one brewery each, North Bend and South Bend. Furthermore, North Bend has a mobile bottling company and South Bend has a stationary bottling company. That’s a total of four beer-related business entities in the County.  Two of these businesses, the North-Bend brewery and the South Bend bottling company, are publicly-owned.

• The CBP publishes five statistics:
  • (A) The total number of employees in beer-related businesses in North Bend: Because there is only one brewing company in North Bend and only one bottling company in North Bend, the category is coarsened to “beer-related”.
    
  • (B) The total number of employees in beer-related businesses in South Bend: Because there is only one brewing company in South Bend and only one bottling company in South Bend, the category is coarsened to “beer-related”.
    
  • (C) The total number of employees in brewing only:  Because there is only one brewing company in each of North Bend and South Bend, the statistic is coarsened to the total number of employees in brewing only in the County.
    
  • (D) The total number of employees in bottling only: Because there is only one bottling company in each of North Bend and South Bend, the statistic is coarsened to the total number of employees in bottling only in the County.
    
  • (E) The total number of employees at publicly owned companies: Because there is only one publicly owned company in each of North Bend and South Bend, the statistic is coarsened to the total number of employees in publicly owned companies in the County. 

We now have 5 equations in 4 unknowns. Using only 4 of these (A, B, C, and E), we can solve for the exact number of employees at each of the four companies with high school algebra.

In the above (fictional but realistic) scenario, the County Business Patterns were released with good-faith coarsenings for the geographical, business, and ownership categories.  Nonetheless, even without inside knowledge of one of the companies’ number of employees, we can completely reconstruct all four numbers.  What happened?  The coarsenings interacted poorly.  Noise infusion perturbs that set of equations, preventing exact reconstruction.

2.      Impediments to Implementation

The Commerce Department now claims the directive’s return to the outdated “tradstat” traditional statistical techniques of the 70s is good for data consumers: “This update to our disclosure limitation method protects respondents and provides the public with more essential economic information.”  (Emphasis added.)  As we saw from Goldschlag’s example, coarsening does just the opposite.

And it can’t be fixed. Coarsening by definition reduces access to fine-grained information.  Our example of three poorly interacting coarsenings shows that this sacrifice is for naught: without noise infusion, confidentiality is destroyed by elementary calculations.  For population surveys, this is precisely what formal noise infusion methods, like differential privacy, protect against; this is the “fancy math” that Goldschlag mentions in his post and that holds personal characteristics, like citizenship status, in confidence.  

3.      Confidentiality is Critical for Federal Statistics 

The scientific community continues to debate the best techniques for protecting the confidentiality of respondents’ data, but DAO-216-26 is not driven by science. It is driven by political interests. Those issuing this order are willing to risk the public’s trust in the process. We think that this is wrong-headed and dangerous. 

Civil servants will do their best to comply with this order while still following the laws that require them to protect the confidentiality of respondents’ data. To balance these competing mandates, they may seek to produce less data or coarsen data so much that it is unusable. Or they might be pushed by political actors to publish data that can be easily unmasked, like in the brewery examples above. Regardless of their choices, they will be hard-pressed to guarantee respondents’ confidentiality, which will prompt many businesses and individuals to simply not answer. This is devastating for an agency that delivers democracy’s data.

Conclusion

Rather than political actors overruling the government’s own statisticians, we need deep investment in our nation’s statistical agencies, ensuring that agencies have the staff and support to improve their methods using the best available tools. Regardless of how the scientific community feels about any specific privacy-enhancing technique, we must collectively reject this anti-scientific approach to governing federal statistics. Too much is at stake. 

How to Take Action

Share this post with others in your professional network and community.

Contact your Congressional representative and voice your concerns. Calling or writing to your representative is one of the most effective and easiest things a constituent can do that should only take a couple minutes of your time.

1. Find your representative contact information here.
2. State your concern. Here is a sample script: “My name is [Name], and I am a constituent from [City] in your district [ZIP CODE]. I am calling because I am concerned about the the U.S. Secretary of Commerce issued a directive (DAO 216-26) that wants to relegate confidentiality protection in all Bureau of Economic Analysis and U.S. Census Bureau data products and statistics to outdated and ineffective statistical techniques. If followed, this order will destroy the Commerce public data our nation relies on for important decisions, such as where to build necessary services for our community’s well-being. I want the DAO to be rescinded. I want proper administrative procedure to be followed. I want technical decisions such as the choice of method used to balance utility and confidentiality to be informed by professionals in the federal statistical agencies, not made unilaterally by political operatives.”
   1. Optional is stating what kind of constituent, such as a retired teacher or a working professional.

Volunteer to help preserve Census working papers and documentation. Pages explaining “noise infusion” and “differential privacy” are already going offline. Archive relevant methodology pages and technical documentation. You can also do this via the Internet Archive’s Wayback Machine (“Save Page Now”).

John Abowd 
Aloni Cohen
Cynthia Dwork
Jae June Lee
Jayshree Sarathy
Adam Smith
Salil Vadhan

---

[1] BEA Working Paper WP2026-9, now purged by the Department of Commerce.  As of 6/22 Google returns:

Bureau of Economic Analysis (BEA) (.gov)
https://bea.gov › files › papers › BEA-WP2026-9

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

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

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

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

---

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

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

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

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

---

So then, how can we win the grand popularity contest against the physicists? How can we, as I put it in my title, spread the gospel of CS theory to a constant fraction of the human race? In my view, the first step is to reframe who we are and what we’re about. We’re not this obscure little community off to the side, proving its little theorems about derandomization and catalytic space. No! What we are is the conceptual and mathematical core of computer science, the field that’s changing the face of civilization in obvious and undeniable ways.

This was even true a long time ago. The physicists had Galileo and Einstein? Well, we had Turing, a figure so heroic and so tragic that no one would’ve believed him as a fictional character. And while we’re at it, we’ll claim Gödel and Shannon and von Neumann, Leibniz and Babbage and Ada Lovelace—they’re all ours too.

That’s our proud history. But then when we turn to today, it’s like, holy crap! Even the densest ignoramus can now see how deep intellectual ideas originating in CS are changing the world.

---

Blockchains—some people might wish they’d never been invented, but they were invented, so we all need to think about how they change the world’s economy for better and worse. And of course, they’re fundamentally based on hardness assumptions; they couldn’t exist in a world where NP was easy.

Part of my outreach job these days is to explain to finance people, over and over, why a quantum computer could break the elliptic curve signature schemes used by Bitcoin and many other coins, but would have only a more modest effect on the proof-of-work part, the hash function. And it’s like, if you actually want to know, then we need to talk about BQP versus NP, Grover’s algorithm and its optimality, black-box problems with and without abelian group structure—and now we’re deep into TCS!

Speaking of quantum computing—even if we set aside the question of whether quantum computing is going to revolutionize materials science or chemistry or pharmaceuticals design—or whether it will revolutionize AI and machine learning and optimization [I shake my head, make a thumbs-down, and blow a raspberry]—even if we set aside those practical questions, quantum computing plausibly represents the most dramatic test of quantum mechanics itself that we’re ever going to see. And it now looks clear that we will see that test within the next decade or sooner. One way or the other, we’re going to learn the truth.

People sometimes ask me, why did it take until the 1980s for anyone to propose the idea of quantum computing? You know, Heisenberg and Schrödinger were in the 1920s, Turing was in the 1930s, so it seems like all the ingredients were in place a half-century earlier! In my Quantum Computing Since Democritus book, I reflected on this, and I think the deepest answer is that not quite all of the intellectual ingredients were in place. Quantum computing is something that it doesn’t make a great deal of sense even to ask about until you’ve established polynomial versus exponential, and even P and NP and NP-hard, as central concepts. And that’s what didn’t happen until the 1970s.

---

But of course, the biggest thing that our CS concepts have unleashed on humanity—the thing that the entire world now realizes holds even greater promise and greater peril than nuclear energy did in the last century—is [pause for effect] the Razborov-Smolensky lower bound method.

No, I’m kidding of course. It’s generative AI.

Twenty years ago, I remember people in our community—was it Fortnow? Impagliazzo? I’m not sure—saying, “you know the real reason why P vs. NP is such an important problem? Suppose P=NP, via an algorithm that was fast in practice. Then it’s not just that you could break all the encryption systems, or have your computer find a proof of the Riemann Hypothesis, or whatever. No, it’s that you could program your computer to find the shortest efficient compression of, for example, the full text of Wikipedia. For in order to create that compression, it seems plausible that your computer would need to create an AGI as a byproduct.”

I remember thinking to myself: “that’s an amusing thought experiment, I’ll need to steal it sometime, but still, what an utterly simplistic vision of the nature of intelligence! There has to be more to intelligence than sheer data compression!”

Fast forward to spring 2022, when I accepted an invitation to go on leave for a couple of years, to join what was then a relatively obscure little nonprofit foundation by the name of … err … OpenAI. When I flew to San Francisco to start my assignment, I had lunch with Ilya Sutskever, the cofounder of OpenAI and then its chief scientist. And Ilya said to me, “Scott, let me explain to you how we think about things here at OpenAI. For us, intelligence is fundamentally about prediction, and prediction is fundamentally about compressing your training data. As you know, Kolmogorov complexity is uncomputable, but one can get better and better computable upper bounds on it. We conjectured that, in order to get sufficiently good at predicting and compressing all the text on the Internet, you’d need to build a model of the entire world that had led to that text being written. And we made a gamble that large neural nets would do that well enough, despite the problem’s worst-case intractability.”

That conversation was when it hit me that, if only we in CS theory had taken our own concepts and thought experiments more seriously, one of us could’ve started OpenAI 15 or 20 years ago. So OK, we didn’t, and that’s why I flew coach to get here. But this is the kind of story that it seems to me we could be singing from the rooftops.

(Incidentally, the reason why OpenAI wanted me back in 2022, was to use theoretical computer science to figure out how to make AI safe for humanity. Alas, that problem is still open! But I’m thrilled that there are so many sessions about exactly this question at STOC this year, and I hope many of you will choose to get involved.)

---

In the rest of this talk, I’d like to offer some advice—such as I have—for any of you who’d like to try your hand at speaking or writing or blogging or podcasting about theoretical computer science for a broad audience. You see how my hair is starting to gray? Yeah, that’s what authorizes me to go into advice mode.

Let’s start with the obvious: meeting the audience where they are. This is something that I learned years ago from Steven Rudich, who along with Luca, was another irreplaceable figure who our community recently lost, and lost too soon. I remember 26 years ago, at that same IAS summer school where I learned from Luca, Rudich gave the students a talk about how to give talks. In it, he showed a cartoon of someone lecturing. And there were little thought bubbles that said:

What the speaker thinks the audience is thinking: MORE! HARDER! FASTER! Ah yes, QED, truth is beauty and beauty is truth!

What the audience is actually thinking: What the hell are they talking about? When is this over? Can I get a date with the person sitting next to me?

You know, this misconception that because something has become obvious to you, after thinking about it for years, therefore it should be equally obvious to your readers or listeners encountering it for the first time? This is what Steven Pinker dubbed “the Curse of Knowledge,” and calls the most fundamental problem of all exposition. (I could mention the related misconception that because something has become interesting to you, therefore it’s interesting to your audience. But you can make just about anything that’s interesting to you interesting to your audience, by telling a suitable story about it.)

What can you do about the Curse of Knowledge? Practice giving a buttload of talks to undergrads, high school clubs, even physicists, and listen to the feedback you get. If the same weird confusion shows up at least twice, it’s a safe bet that it’s going to keep showing up—which means, now you can anticipate and preempt it the next time you explain the same concept.

But it’s not just misconceptions that you should listen for. Listen for which of your metaphors and anecdotes actually land. Certainly listen for which of your jokes get a laugh. Use those more the next time. And if saying, for example, “hur hur, I’m in a quantum superposition of two different topics that I could talk about next”—if that fails to get a laugh, then DROP IT.

Eventually, you’ll build up what Carl Sagan once called “consumer-tested stepping stones”: that is, a library of jokes, anecdotes, and metaphors that can get you from wherever you see the audience is to wherever you need them to be. Here’s an intentionally tiny example of one of my stepping stones: “Why is P contained in NP? Because the verifier just says to the prover, dude, take a hike, you’re not needed here.” Or another stepping stone, for when we reach the question of the likelihood of P=NP: “look, if we were physicists, we would’ve declared P≠NP to be a law of nature. We would’ve given ourselves Nobel Prizes for the discovery of that law. And if it later turned out that P=NP? We’d just give ourselves more Nobel Prizes for the law’s overthrow!”

---

This brings me to a broader point. CS theory is unusually rich with facts that are true for silly or absurd or ironic reasons. Lean into that! Don’t hide it!

I mean, “if NP has small circuits then this theorem is true, but if NP doesn’t have small circuits, the theorem is again true, but now for a totally different reason”? That’s sidesplittingly hilarious! OK, maybe only to some of us.

Or why does IP=PSPACE? An alien lands and is like, “I COME TO EARTH TO TELL YOU THAT WHITE HAS THE WIN IN YOUR GAME CALLED CHESS.” And we’re like, “why should we believe that?” So the alien is like, “LET US PLAY A GAME. I’LL PLAY WHITE AND WILL WIN.” And we’re like, “oh, we assume you’re smarter than us! You came all the way here in a spaceship and all! But that still doesn’t prove it.” So the alien is like, “THEN LET US PLAY A DIFFERENT GAME, MATHEMATICALLY EQUIVALENT TO CHESS, INVOLVING SUMS OF POLYNOMIALS OVER A FINITE FIELD. IN THIS TRANSFORMED GAME, THE BEST YOU CAN DO IS TO MOVE RANDOMLY. SO IF I STILL WIN, YOU’RE STATISTICALLY CERTAIN I WOULD’VE WON REGARDLESS OF HOW YOU PLAYED.” It’s like, dude. Dude!

Of course, our founding irony, our founding absurdity, was self-reference and diagonalization. Like, “you can’t predict what any human brain will do 5 seconds from now, because if you could, you could predict what you yourself were going to do 5 seconds from now, and then do the opposite of that!” BOOM! Therefore the halting problem is undecidable and the Time Hierarchy Theorem is true, QED. But beyond that: “black-box program obfuscation is impossible, because one thing you can always do, if given the actual code of a program, is to run the program on its own code and see what happens.” Dude! Or: the reason why it’s so hard to prove P≠NP, is that it’s presumably true that P≠NP. That’s a wisecrack that, in the context of the Natural Proofs barrier, becomes so much more than a wisecrack.

One special case of leaning into absurdity concerns the central role in our field played by asymptotics. I’m always slightly at a loss when someone asks me, “so, how many times faster would a quantum computer be than a classical computer? A million times faster? A billion?”

Part of me wants to reply: “I must educate you about polynomial versus exponential scaling until you see the profound error of your question, and retract it.” But another part of me simply wants to say: “depending on the problem, a quantum computer could be anywhere from not faster at all to, let’s say, 10¹⁰⁰⁰⁰ times faster.”

The truth is, I think we need to do both. Anytime you’re talking about asymptotics to laypeople, if you can plug in some representative numbers, it will help them understand what you’re talking about. And then, if the asymptotics are what really control the real-world numbers, so much the better! If, on the other hand, the asymptotics are comically disconnected from the real-world numbers—if, for example, you’re trying to improve something from log*(n) to Ackermann^-1(n) or whatever—well then, you can lean into that as an additional source of humor.

---

Alright, one last piece of advice. Tell true stories about how you came to understand or discover whatever it is that you’re talking about. Don’t be like the mathematicians who love to cover their tracks.

When people ask me how I proved the lower bound on the number of steps needed for a quantum computer to find collisions in a list—a centerpiece of my PhD thesis, and one of the two or three hardest technical things I’ve done in my career—I say, look, I was 20 years old and I had no social life. So I just pulled many all-nighters trying every possible approach. Eventually, I came across some complicated expression that had no right to be a polynomial. But somehow, every term in the denominator cancelled against a corresponding term in the numerator, and it was a polynomial! And that let me use the polynomial method to prove a lower bound. Why was it a polynomial? I still don’t really understand, a quarter-century later! My point is, people want the truth.

The secret of blogging is that, even if people despise what you’re saying, even if they think it’s wrong, offensive, problematic, cringe, you name it, they need to trust that you’re telling them the truth of what you know or believe or remember about the subject at hand, the same as you’d tell your closest friend.

---

In summary: we, the CS theory community, are sitting on top of one of the greatest conceptual and intellectual goldmines of our whole civilization. I exhort everyone here: please help tell the world about it! As you do so, think about how to honor Luca’s memory and make him proud. But also think about how to make me, and my silly little blog, superfluous and obsolete.

Thank you for this honor, thank you for the incredible privilege of being part of the CS theory community, and thank you for listening.

One of the most popular posts in this blog’s history was Common Knowledge and Aumann’s Agreement Theorem, based on a lecture that I gave to high-school students 11 years ago. One of the impacts of that post, I’m proud to say, is that (according to Steven Pinker) it helped to inspire Steve’s excellent recent popular book, which you should read, entitled What Everyone Knows That Everyone Knows…: Common Knowledge and the Mysteries of Money, Power, and Everyday Life.

Two weeks ago, I was privileged to attend a workshop in Paris on “50 Years of Agreeing to Disagree,” where (among other things) I got to meet the 96-year-old Economics Nobel Laureate Robert Aumann for the first time.

I got to catch up there with Steven Pinker as well, who gave a phenomenal talk on the psychology of common knowledge. My own talk was entitled The Complexity of Agreement, with New Directions and Applications (link goes to my PowerPoint slides).

Aran Nayebi has graciously posted on YouTube some partial video from the meeting, including his talk, brief snippets from my talk, and Aumann’s own remarks:

Meanwhile, here were the Aumannian insights that I remembered to write down:

AUDIENCE QUESTION: What questions did people ask you after you published your famous agreement theorem in 1976?

AUMANN: I don’t remember what happened yesterday, let alone 1976.

Also:

ME: I thought you might enjoy knowing that I just came here from a meeting of rationalists…

AUMANN: A meeting of who?

ME: Rationalists, they call themselves, at a beautiful venue called Lighthaven in Berkeley, and that they named the main building there “Aumann Hall” in your honor.

AUMANN: OK, so I’ve made it then.

One recent result announced at the workshop, for those who care, is that the proof of Aumann’s Theorem has now been formalized in Lean, by Scott Kominers at Harvard and a group from the startup company Axiom Math.

Thanks so much to Christina Katt-Pawlowitsch, Ziv Hellman, and others for organizing the workshop and for including me in it.

Happy to field questions in the comments, although if someone wants to call me an idiot like usual, we’ll just need to agree to disagree!

I’ve been getting emails from journalists asking me to comment on the new White House executive order on quantum computing. Alas, I don’t have time for a long response or interviews since I’m at a beautiful science camp in the California mountains, and heading soon to STOC’2026 in Salt Lake City. But I gave anyone who asked me the following statement, which I thought might be of interest to readers of this blog as well.

“I hope that at least some of the new funds made available from this Executive Order will go to basic, curiosity-driven academic research — the kind that led to the idea of quantum computing in the first place, and to the main quantum algorithms and other advances that everything builds on today — and not only to large organizations that have gotten good at capturing federal funds by repeating the requisite buzzwords.”

Since I’m a good mood today—at a beautiful science camp with my kids, high in the mountains near Big Bear Lake in California—I thought I’d blog about something positive. Last week, five authors (Chatterjee, Ghosh, Gurjar, Raj, and Thierauf) posted a major paper to the Electronic Colloquium on Computational Complexity, which shows (or anyway, credibly claims to show) that the Bipartite Matching problem is in the complexity class NC. Assuming this stands, it resolves a central problem in parallel algorithms and derandomization that’s been open since the 1980s.

In Bipartite Matching, you’re given a list of n men and n women, you’re told who’s willing to date whom, and your goal is to

1. decide whether it’s possible to pair everyone off with a willing partner, and
2. if they are, actually pair them off.

One of the great early discoveries of combinatorial algorithms, taught in every introductory algorithms course, is that this problem is solvable in time polynomial in n, even though the naïve, brute-force approach would require examining n! possibilities.

(Note that in the bipartite version, we assume that the men and women are all straight. If the men and women can be LGBT, we get the problem of matching in general graphs, which again turns out to be solvable in polynomial time, but now the algorithm is much more sophisticated, and was a major discovery of Edmonds in the 1960s.)

Anyway, the question is whether we can do even better than polynomial time: in particular, can we solve the problem in time polynomial in log(n), given polynomially many parallel processors?

Back in the 1980s, first Karp, Upfal, and Wigderson, and then (via a very different method) Mulmuley, my former PhD adviser Umesh Vazirani, and Umesh’s brother Vijay Vazirani managed to show that the answer is yes, but only if the parallel processors additionally get access to random bits, and only need to succeed with high probability.

The new achievement is to derandomize the Mulmuley-Vazirani-Vazirani algorithm, and show that problems 1 and 2 above are both solvable in deterministic polylogarithmic time with parallel processing (in other words, in the complexity class NC).

No, I don’t understand how it works yet. If anyone does, feel free to explain in the comments! Or ask your favorite AI to generate a summary. If I run out of options, at some point I might actually try reading the paper.

(Note: Thanks to Gil Kalai for some corrections to an earlier version of this post.)

---

One other announcement: Today is the day of primary elections in NYC! Virtually all of my smartest friends who work on AI governance and safety are extremely excited about the Congressional campaign of Alex Bores—indeed, it would be little exaggeration to say that they consider him the last best hope of humankind. Bores has been a national leader on trying to regulate AI, to the extent that Marc Andreessen’s “Leading the Future” anti-AI-regulation PAC has spent millions of dollars trying to sink his candidacy. Outside of AI, Bores seems like a sane, conventional Democrat, i.e. the kind I like, and much more moderate than his base on Israel (note that his main opponent is also such). Without commenting on Bores’ views on every possible issue, I’ll simply say: if you live in New York’s 12th Congressional District (comprising a huge chunk of central Manhattan), and you care about AI safety, please consider a vote for Bores while there’s still time.

In 2024, at the same time as I was being called a genocide apologist, Zionist baby killer, etc. etc., I was also being hounded by my right-wing, pro-Israel readers, who demanded of me: knowing what you know, understanding what you understand, how could you possibly vote for Kamala Harris? How could you donate to Kamala’s campaign, urge your readers to vote for her, when she (like most Democrats) is obviously beholden to young left-wing activists, and young left-wing activists’ central unifying cause has become the death of “Zionists” like yourself and your children? Can’t you see that, even if Trump is a raging, lying, bullying, incoherent monster, at least he’s our monster?

This view, I confess, gave me more pause than “just accept that the liberation of the world’s oppressed requires Israel’s annihilation and hence the death of much of your family,” which my far-left critics considered their most persuasive argument. And yet I also rejected, with extreme prejudice, the right-wingers’ constant invitations to join their MAGA brigade. I replied: I’ll simply continue being a moderate Enlightenment liberal, transported here in a block of ice from the 1990s, even if I’m the last such on earth, even if I’m condemned by everyone on either side for it.

Why? Because, I said at the time, while I’m honest enough to admit when a rampaging T-Rex happens to do something that aligns with my interests—when, e.g., it chases away some velociraptors ready to slice me open, or cracks down on antisemitic fanatics trying to dominate the universities where I spend my life—still, I’ll never delude myself into imagining the T-Rex my ally. I understand that it would just as soon devour me. If the monster goes after my enemies not because of liberal principles or recognizable moral emotions, but just raw self-interest and ego gratification, then what happens the instant its perceived self-interest changes?

It gives me no pleasure that this week Trump proved my instincts here 3,000% correct, by fully capitulating to the Islamic Republic of Iran, far more so than Barack Obama ever did, or than President Kamala Harris ever would have. Trump has now abandoned both the Iranian and the Israeli peoples to suffer and die at the hands of the IRGC, as he abandoned the Ukrainians and the Venezuelans before them, as Neville Chamberlain abandoned Czechoslovakia. All because of the price of gas and the midterm elections.

On the most charitable reading, Trump gambled that taking out Ayatollah Khamenei would lead to a cowed and compliant puppet regime, as basically happened in Venezuela, with no need for a ground invasion or arming the Iranian resistance. His gamble predictably failed, because (alas) the Iranian government actually believes in something—horrifying and medieval though it is. Trump was unable to process that fact, because he’s never believed in anything beyond himself, and he wrongly assumes that everyone else is the same.

With the $300 billion and control over the Strait of Hormuz, I expect that Iran will rebuild its military and proxies to stronger than they were before Trump’s idiotically mismanaged war. I expect that Iran will then launch attacks against Israel that make October 7 look like the Little League—and that, when it does so, a large fraction of the Western world will ecstatically cheer, as it did on October 7 itself. Netanyahu is a fool for expecting otherwise from Trump, a man who’s betrayed everyone who’s ever trusted him outside possibly his immediate family.

I salute those Israelis who will choose to stay and fight even after their abandonment and betrayal, in the spirit of the Bar-Kochba revolt and other desperate battles of Jewish history. Despite the existential danger that Israel will soon be in, facing a victorious and emboldened Iran essentially alone, I also see it as possible that Western countries will rapidly become even more dangerous for Jews than Israel. If that happens, I’ll be grateful that Israel still exists, that it considers itself unbound by America’s surrender, and that I’ll be able to seek refuge there, as was the idea when Israel was founded.

At the same time, I wouldn’t begrudge any Israelis who moved to the US, or Switzerland, or whatever other country will take them. As in the 1930s and at countless other points in Jewish history, the priority now is physical survival, wherever that turns out to be possible.

With hindsight, I spent the first half of my life in a strange interregnum, wherein Jewish history seemed to have finally ended. Now, fueled by fading memory of the Holocaust and by the greatest lie-amplification technologies the world has ever seen, the history I learned as a child has come roaring back. Jews, as they have for millennia, look out on a world of murderous enemies and fickle friends. It’s just the restoration of a norm.

---

Incredibly, abandoning both the Iranian and Israeli peoples to the Revolutionary Guard might not have been the most shortsighted or catastrophic thing Trump did in the last couple weeks. Another candidate would have to be Trump’s attempt to destroy Anthropic (and as collateral damage, American AI development more generally), transparently to punish Anthropic for the crime of having any principles that it was willing to put ahead of obedience to Trump and Pete Hegseth. Specifically, the White House forced Anthropic to pull Fable, its new flagship model (and the “safe” version of Mythos), off the market just a few days after customers had started using it, by subjecting it to export controls that it knew were impossible to enforce. Even the many foreign nationals who work at Anthropic are no longer allowed to use their own model (!). A plausible consequence is that those foreign nationals will stop working at American AI companies altogether, and will move to China or whichever other country rolls out the red carpet for them.

For AI accelerationists, you’d think that this would be a worst-case scenario: a direct government crackdown on AI that goes beyond anything the AI safetyists had proposed, and that indeed would’ve sounded like fantasy even a year ago. And yet many of the accelerationists are gleeful. Why? Because Anthropic, in supporting reasonable AI regulations, had made itself the accelerationists’ enemy. So, the accelerationists’ attitude now is quintessentially Trumpian: “Haha, Anthropic, you say you like regulation? Then take that!” Never mind that whatever dangerous behavior can be elicited from Fable, can almost certainly be elicited as well from GPT 5.5 Pro, and yet there’s no talk of any similar crackdown against OpenAI. Sam Altman, after all, donated $1 million to Trump’s inaugural fund. No one finds it remarkable anymore, in Trump’s destroyed and recreated United States, that your rights depend entirely on your standing with the Don.

And so, just like the question of whether Trump would side with the isolationists or with the hawks who wanted to liberate Iran, was resolved by his worst-of-all-worlds choice to surrender to Iran, so too the question of whether Trump would hit the brakes on the race to dangerous AI, or accelerate in order to beat China, has been resolved by his worst-of-all-worlds choice to lose the race to China. I.e., we’re still in full race mode, but we’re also going to do whatever we can to lose the race—by, for example, letting NVIDIA sell its chips to China, and now, scaring away our top researchers and punishing our AI firms with capricious and arbitrary crackdowns.

---

It’s disconcerting to reflect that, while the prognosis of the world is arguably the worst it’s ever been in my lifetime, my own life is pleasant. Intellectually I know that the Titanic has already hit the iceberg, but the band is still playing and I’m still being served delicious food.

Last week I visited Paris and the French countryside with my wife and kids. In addition to sightseeing, I spoke at a workshop celebrating 50 years of Aumann’s Agreement Theorem (where I got to meet the 96-year-old Aumann), and gave a quantum computing talk at the Sorbonne. Next week I’m going with my family to a science camp in California, then to STOC in Salt Lake City, where I’ll accept the Trevisan Prize and give an after-dinner speech, then to Epsilon Camp where I’ll again teach theoretical computer science to 11- and 12-year-olds.

Like I said, life is good here on the Titanic, if you ignore the rapidly rising seawater at your feet.

The comments on my previous post, on recent AI breakthroughs in solving Erdös problems and beyond, must’ve set some sort of record for the number of separate reasons commenters offered me to despair about the future of humanity. All this in a post that I saw as relatively nerdy and anodyne, goring few oxen, when I clicked “Publish”!

According to some persistent commenters, the only reason why I wrote about recent AI-enabled math breakthroughs is that I’m a shameless shill for the AI companies, my loud public criticisms of those companies being nothing more than a cynical smokescreen. Except that I’m also a laughable dupe of the AI companies.

See, AI, despite all appearances to the contrary, has not solved the Erdös unit distance problem or any other important math problems at all. It’s merely produced vast amounts of garbage via brute-force search, and then human mathematicians, sifting through the digital garbage pile, found some things they could call “proofs.” Except also, those human mathematicians aren’t even real mathematicians! They’re merely Hungarian combinatorialists, the kind obsessed with trivial, uninteresting Erdös problems, which it stands to reason that AI can now solve. AI will never touch the truly deep, creative parts of math, epitomized by Grothendieck-style algebraic geometry.

(When I relayed this to a world-leading algebraic geometer of my acquaintance, he laughed and said that everyone has to tell themselves whatever it takes to cope with the situation. He himself has been using LLMs in his research, and while they can’t yet write his papers for him, he expects them to improve very rapidly.)

When pressed, my commenters made it explicit: Timothy Gowers, the Fields Medalist who told his fellow mathematicians that he hopes they’re sitting down before he broke the news about the Erdös distance problem, is not a real mathematician, just a combinatorial puzzle-solver. Paul Erdös himself was not a real mathematician either.

Oh, and also, I’m a genocidal Judeofascist Zionist. That entered the comments as well, with the pretext being that I had shared a GPT-written story about ancient Israelites.

(Note: For every comment that I allowed to appear in the thread, assume as usual that there are many worse ones that I didn’t.)

Does anyone wonder why I blog so much less than I used to? Seeing what humanity has to offer, as reflected in my comment section, I feel like maybe we should take our chances with our future AI overlords. Except that some of my comments are—ironically, given their content—likely to be AI-generated as well.

These days friend after friend of mine, colleague after colleague, acquaintance after acquaintance is becoming a multimillionaire or even a billionaire from startup equity. Meanwhile, I’ve scrupulously abstained from all of that.

Why? Well, probably the single biggest reason has been Shtetl-Optimized. I’ve zealously sought to protect my “neutrality” and “objectivity” as a commentator, on this free (and even ad-free) public forum—the one where I try every week to reason with anonymous trolls with “proton.me” email addresses who show up to call me a hack and a shill and a baby-killer and a dunce. Ironically, the actual billionaires who I know hardly ever get called those sorts of names, mostly because they don’t offer the world a huge attack surface like I do. Or if they occasionally do get called them, they don’t care.

On reflection, all the commenters calling me a dunce have a point. When one looks at how I chose to spend my life, versus how all these billionaires did, I am kind of a moron.

---

And yet I titled this post “On Hope.” In a situation like the present, one needs to find hope wherever I can. And right now, I’m choosing to find it in this open letter, which has been signed by over 1,250 professors at the University of California. Let me quote the beginning of it:

To the UC Regents, UCOP, Academic Senate leadership, and the people of California:

We write as University of California mathematics faculty, joined by faculty from other STEM disciplines. UC has long served students from every background and has been a powerful engine of social mobility for the people of California. That public trust must be protected for future generations. Today, UC’s mission is at risk. To preserve that mission:

We call for the reinstatement of the SAT/ACT mathematics requirement for applicants to STEM majors beginning with the 2027 admissions cycle, alongside STEM faculty oversight of readiness standards and admissions practices affecting those majors.

Over the past five years, we have seen a widening divergence in mathematical preparation levels within the same classroom. This trend indicates that current admissions practices do not provide a sufficiently reliable check on mathematical readiness for STEM majors. The UC San Diego Senate–Administration Workgroup on Admissions report documents this crisis in stark terms: in the last five years, the number of students whose mathematics skills fall below high school level increased nearly thirtyfold; moreover, 70% of those students fall below middle school levels, reaching roughly one in twelve members of the entering cohort. These findings are corroborated by data across our campuses…

Everywhere one looks right now, and on every part of the political spectrum, doofuses and blankfaces strut across the earth triumphantly. Yet there remain pockets of sanity. What reading this open letter told me is that the University of California STEM faculty is one of them.

With enough such pockets, I could live a perfectly reasonable rest of my life, from now until my natural death (or until AI changes all our lives beyond recognition), regardless of who shows up in 3 … 2 … 1 … with a “proton.me” email address to confidently tell me otherwise.

As most readers have presumably heard by now, Paul Erdös’s Unit Distance Problem from 1946—one of the central open problems from the field of discrete geometry—has been solved by an internal OpenAI model. Erdös had conjectured that, given n points in the plane, at most n^1+o(1) pairs of them could be unit distance apart. Using high-powered results from algebraic number theory, GPT refuted this, constructing a set with n^1+ε unit-distance pairs, for ε ~ 10^-38. Shortly afterward, Will Sawin, a human (!), improved GPT’s construction to get ~n^1.014 pairs. There’s since been a claim to improve this further, to ~n^1.034. Meanwhile, the best known upper bound remains n^4/3, improving Erdös’s n^3/2.

The entire process seems have been one-shot: my former student Lijie Chen simply gave GPT the problem, then GPT thought for a while and output a several-page argument that, on analysis by human experts, turned out to be correct. Of course there’s selection bias here; we’re not hearing as much about the hundreds of other problems GPT was given that it didn’t solve (isn’t that the case with humans too?). Clearly, too, GPT was helped by the facts that human mathematicians had wasted most of their time trying to prove Erdös right rather than looking for a counterexample, and that, even if they did look for a counterexample, they’d need to be experts in algebraic number theory to find this one, which hardly any discrete geometers are. So, maybe that suggests that AI, right now, is “merely” picking various medium-hanging fruits that human mathematicians missed for contingent reasons? With emphasis on the “right now.”

In a companion paper, OpenAI helpfully included commentary from Timothy Gowers, Noga Alon, Will Sawin, Daniel Litt, and many other experts, reflecting on the breakthrough, the path that GPT took to get to it (which can actually be seen by examining its chain-of-thought), and what this might mean for the future of mathematical research.

I heard the news maybe an hour after it broke, when some UT grad students came to my office to tell me. For what it’s worth: these students were morose, musing about how everything might soon be over for young scientists and mathematicians like themselves. I don’t know whether they’re right, but I feel like I should tell the truth about what their reaction was.

[Update: News has been coming faster than I can write about it, but today we learned that another important conjecture of Erdös has been refuted. Erdös and Szemerédi’s strong sumset conjecture over R, from the 1970s, had said that, if A is a finite set of real numbers, then either |A+A| or |A×A| must be at least |A|^2-o(1). In this case humans, including the aforementioned Sawin, did almost all of the work of constructing the counterexample, but they were directly inspired by GPT’s earlier refutation of the unit distance conjecture. It remains open whether such a counterexample exists where A is a set of integers.]

Then, a few days later, a team at DeepMind, including my UT Austin colleague Swarat Chaudhuri, announced that they were able to use a system called AlphaProof Nexus to settle nine more (!) Erdös problems, many of them in additive combinatorics, along with miscellaneous other open math problems. Notably, in this case the AI also fully formalized its proofs in Lean.

And then, just today, Jelani Nelson alerted me to a new CS theory paper, which solves a longstanding open problem about electrical flows on graphs using a proof from GPT5.5Pro.

It seems to me that we’re now over the top of this particular rollercoaster, and it will keep accelerating until we reach the bottom, wherever that might be. I don’t know whether to hope or dread that solutions to P versus NP and all our other great problems will be included in the ride—that our role, as human mathematicians, will be reduced to (at most) deciding which questions we find interesting and then understanding AI models’ answers to those questions.

But maybe that won’t happen. Maybe the new AI mathematicians will soon hit a wall, because they lack the uncomputable quantum gravity microtubules of Penrose and Hameroff, or some other magic human ingredient. The fantastical thing is that, one way or the other, we’re going to find out empirically before very long.

---

Readers may have also seen the news that multiple prizewinning entries in a short fiction contest called the Commonwealth Prize, give overwhelming indications of having been written by AIs. As Kelsey Piper puts it:

There are, let’s say, also some noticeable similarities in the prose style between the winning stories that were flagged for AI use. AI chatbots love metaphors and similes, and they often spit out ones that sound vaguely pleasing but are logically incoherent or ascribe properties to things that don’t make sense.

“The Serpent in the Grove” gave us, “The girl smiled like sunrise over a sink.” “The Bastion’s Shadow” says, “She carried it now in her bag, heavy as a charm.” “Mehendi Nights” describes something as “swaying against plaster like a warning bell.”

The Commonwealth Foundation, whose judges chose these stories, hasn’t exactly covered itself in glory—saying, on the one hand, that it strictly forbids AI use but on the other, that it will continue taking authors at their word that they didn’t use AI, no matter the immensity of evidence to the contrary. As many others have pointed out, judges more versed in AI would’ve ironically been better placed to notice the signs of its use.

If only there were some sort of automated way to detect AI-generated text. Someone should really get on that problem, don’t you think?

---

But maybe we should just throw in the towel—as some of my colleagues have already done in the context of undergraduate projects? Maybe we should simply say that a good story is a good story, regardless of what manner of entity produced it?

As it happens, just last week I read my very first AI-written story that affected me as a story, to the extent that I wanted to read it more than once. This happened when I gave GPT5.5Pro the following simple prompt:

Write me a story about the most ancient Israelites that’s riveting like the stories of the Bible but that’s also consistent with all of the archeological evidence.

You can read the result here. One of my Facebook friends called it “disturbingly good,” and whatever the problems with the piece, I share that feeling. Of course, I’m well aware that GPT could easily generate a thousand stories like it—sampled from the same probability distribution—and then I could even do statistics on which tropes were the most common. This makes it feel silly to overindex on the first story that happened to be output, and yet somehow I did.

---

I feel like at this point, both the prophets of AI utopia like Ray Kurzweil, and of AI doom like Eliezer Yudkowsky, could be forgiven for asking: dude, will you listen to us YET? Do you still find it prudent to call this new form of terrestrial intelligence a stochastic parrot, a laughable fraud, or a fad that’s about to go away? Fear it all you want, hate it even, but at least respect it!

Which brings me to the other big AI news from the past week, namely that Pope Leo released his first encyclical, which is entitled “Safeguarding the Human Person in the Time of Artificial Intelligence.” I read it and … well, I certainly agreed with the theme that such a world-changing technology needs to be developed for the common good (as the Pope would have it, like the walls of Jerusalem), rather than for the profit or vanity of any one individual or company (in his analogy, like the Tower of Babel). I had quibbles with some of the other parts. Zvi Mowshowitz, as he often does, had a superb paragraph-by-paragraph analysis. Amusingly, there are indications that parts of the encyclical were written by AI.

To me, though, maybe the most notable part was that Chris Olah, who leads Anthropic’s interpretability team, was standing next to the Pope at the ceremony, and delivered his own remarks. I felt like Chris, who I met even before Anthropic existed, was a non-obvious yet inspired choice here, one of the rare figures in frontier AI whose technical and moral authority are both completely unimpeachable by anyone.

And so, at this momentous era for the human project, and on no less of an authority than that of the Vicar of Christ himself, the Supreme Pontiff and the Successor of Peter, I hereby throw myself on the wisdom and mercy of … uhh, I guess, Chris Olah and his team at Anthropic.

Chris, if I am soon to share the earth with entities that can prove the Riemann Hypothesis and solve quantum gravity after 30 seconds of thought, then may you understand those entities well enough to cause them to be nice.

---

Endnote: I should have foreseen, but didn’t, that the comments on this post would be dominated by people looking for ways to minimize whichever specific AI accomplishments I blogged about. Thus, it turns out, the ability of AI to solve Erdös problems just demonstrates that Erdös’s problems were never “serious” math in the first place—nothing like algebraic geometry or Grothendieck-style theory-building, which remain untouched. Likewise, the story I shared was obvious AI slop.

I had taken it as obvious that, when assessing AI’s impact on the world, one needs to look at least somewhat into the future: to remember where things were four years ago, compared to where they are today, and at least try to draw a straight line through the data, if not the exponential that seems to fit better.

Does anyone seriously doubt at this point that major open problems in algebraic geometry and other “Grothendieck-friendly” areas of math will fall to future AI models? Or that AI-written stories will improve, not only to win literary awards from AI-naïve judges, but to avoid the features that commenters here are complaining about? And that, whenever that happens, there will be new confident reasons not to care immediately offered up in comment sections like mine?

Apparently people do still doubt—hence the throwaway remark in my post about Penrose and Hameroff and microtubules. If not that or something like it, what exactly do they think the ceiling will be, and why?

Recently (I should have mentioned this before), I came across what I consider one of the greatest social experiments of all time, one that illuminates people’s reactions to every AI advance. A Twitter/X user named SHL0MS displayed the following AI-generated fake “Monet painting,” and asked people to explain what made it worse than real Monet paintings:

If you haven’t seen this yet, I recommend that you try the exercise yourself before reading further.

As it was, numerous art aficionados responded at length, savaging the flat, lifeless, uncreative AI slop, the emotionless composition, the missing spark, the lack of tranquility, the harshness, the lack of depth and symbiosis, and on and on and on.

Only after they had all said their piece did SHL0MS reveal that this is an actual Monet painting.

Over the years, I’ve written two op-eds for The New York Times about quantum computing, at the NYT editors’ invitation:

• Quantum Computing Promises New Insights, Not Just Supermachines (2011)
• Why Google’s Quantum Supremacy Milestone Matters (2019)

I’ve also visited the NYT office and helped NYT reporters with numerous stories about quantum computing and beyond. In the wake of Cade Metz’s infamous NYT hatchet job against Scott Alexander and the rationalist community, I resolved no longer to talk to Metz, but it never even occurred to me to extend that to a broader ban against the NYT itself. After all, it’s the friggin’ NYT!

This week, however, Nicholas Kristof—a man who I praised fulsomely in a blog post 20 years ago, for his coverage of the genocide in Darfur—has used the NYT to broadcast the oldest, crudest form of antisemitic libel, accusing the Jews of garishly preposterous crimes (poisoning wells? baking blood into matzo? in this case, training dogs to rape prisoners). As countless others have since pointed out, the sole source for this ludicrous accusation was a Hamas-linked organization called “Euro-Med” that praised the October 7 “martyrs.” Kristof’s piece came out the same day an Israeli human rights organization released a major report meticulously documenting Hamas’s mass rapes on October 7–something that did happen—and was apparently designed to neutralize the impact of that report.

While the debunking of Kristof came fast, it wasn’t fast enough: now that antisemitic blood libel (dog libel?) has the Gray Lady’s imprimatur, I expect it to ignite violence against Jews all over the world, and I expect my kids to be less safe. So I hereby announce:

I, Scott Aaronson, member of the National Academy of Sciences, will no longer cooperate with anyone from the NYT on anything—neither quantum computing stories nor anything else—until the NYT, at minimum, formally retracts its dog-rape claim and fires Kristof.

To my friends doing good science and technology writing for NYT: I’m sorry, I hope you understand, and please fight for what’s right within the organization.

I say “bare minimum” because I hope this scandal causes a major reckoning for the NYT as an institution. I don’t know if any libel or other laws were broken, but if they were, I hope Kristof personally and the NYT as a whole get sued for whatever they’re worth.

---

Luckily, others have already said most of what I would’ve wanted to. Here’s Eli Lake, in a passage that part of me wishes I’d never read:

Let’s start with what is known about the biology of male dogs. Their penises are small and thin. They become erect only when they smell the pheromones of a female dog in heat. Brandon McMillan, the three-time Emmy-winning host of CBS’s Lucky Dog, who has spent 25 years training animals, told me he had never heard of a dog who was trained to rape a human being and doubted this was possible.

“When a female is in heat, the pheromones released carry it to the male canine,” McMillan said. “That’s how they reproduce and the miracle happens. I don’t see how you would train a dog to do that. The dog has to get turned on, for lack of a better word.”

[Note: Several people wrote to me to push back on McMillan’s claim, citing cases in the medical literature where people got injured engaging in bestiality with their male dogs, which did have erections with no female pheromones needed. But it seems that no case, in the whole vast medical literature, describes a dog being trained to mount humans and rape them.]

On the NYT’s “vetting process” (or lack thereof), here’s comedian Jeff Maurer:

Imagine that you’re a fact checker or editor at The New York Times. You know damn well that you’ve nabbed a lifeboat while most of your field is being picked apart by hagfish at the bottom of the North Atlantic. If you’re a lowly fact-checker, you might be in your 20s and desperate to rationalize your choice to enter a field that might as well be buggy repair. I‘ve had similar gigs and been in similar environments; I feel like I can get in these peoples’ heads. And that’s why I’m convinced that the dog claim should have made things easier for the fact checkers.

One day, Nicholas Kristof — the award winning columnist who has been with the Times since it was Farmer Sulzberger’s New Amsterdam Seed Catalogue — comes to you, the lowly fact checker. He’s working on a big piece, and it’s scorching hot: It’s sexual assault plus Israel/Palestine, which is like detonating a nuclear weapon inside a volcano. You know it will be very tough to say “I don’t find this source credible” or “we can’t run that without more substantiation”. And that’s true even before we consider that you probably run in a social circle in which Israel is thought of as a substantially-more-evil version of The Borg Collective from Star Trek (which is why they have those vaporizing weapons).

But you do notice that Kristof’s sources are thin. In fact, he only has two named sources. The first source tells him a story that has substantially changed since he told it to The Washington Post two years ago. The second source celebrated the October 7 attacks and previously made torture claims that he later recanted. Much of the testimony contains no detail that could be corroborated. The organizations and journalists that Kristof relies on are highly dubious and engaged in the mutual citation circle jerk that is typically the way that lies enter the zeitgeist. There may be some truth in there somewhere, but Kristof’s methods are — what’s the journalistic term? — total ass. But you’re afraid that if you question things, you’ll be thought of as pro-rape, or worse yet: pro-Israel.

And in that context, the dog story is a godsend. It frees you from addressing the broader problems with the article, because you can pick the battle of focusing on the most-outrageous, least-believable claim. The article doesn’t need the dog rape detail — it’s already full of shocking-if-true claims. Striking that one section lets you maintain a sheen of professionalism, and when the thing explodes, you also get to say “You should have seen what he wanted to print”.

The fact that that didn’t happen tells me that the level of scrutiny for claims about Israel at the Times is absolute zero. Even if some Israeli somewhere did manage to turn his dog into a sex criminal, there is not nearly enough evidence for that claim to run in the Times. It’s an unsubstantiated rumor, and a vile one. I think that a person who believes that without compelling evidence is showing evidence of a damaged mind. And I think that a newspaper that publishes that without compelling evidence is showing evidence of a damaged vetting process, or perhaps a vetting process that — when it comes to claims about Israel — doesn’t exist at all.

Last but not least, here’s Haviv Rettig Gur, with righteous anger entirely appropriate to the situation, yet also a determination to expose and fight prisoner abuse, which is a genuine problem in Israel as it is in pretty much every other country on earth:

No, dogs aren’t being trained to systematically rape prisoners, you nattering halfwits. And no, Hamas propaganda operatives are not reliable sources on the question of Israeli crimes. The vast, vast majority of soldiers are honorable men who walked into fire so our families may live. The whole world may turn on them; I will stand with them, grateful for their sacrifice. And Kristof, a willing purveyor of propaganda happily feigning that he can’t see the water and thrilling to a moral crusade engineered by would-be genocidaires he pretends not to understand — is no messenger of moral reckoning.

But friends, so fucking what. Let the narcissistic guttersnipes strut their moral emotions before the world, let the UN publish endless reports that don’t hold up to basic scrutiny, let the NGOs dream their rabid, sick dreams that no journalist ever fact-checks — yes, they’re lying. But so fucking what.

We still, for ourselves — because fuck them — must see that it isn’t all fake. The problem [of abuse in Israeli prisons] is real. It’s far smaller than they claim, but real nonetheless. And when discipline and morality break down, it can only get worse. We either crack down now or we watch it fester and grow.

And our own Ben Gvirs are stubbornly refusing to fix what is actually broken, the real thing in the real world.

And so we are caught in a strange sort of vise, the same vise we find ourselves in with the genocide lie: A vast propaganda machine that seeks to destroy us — countless activists too high on their own self-regard to see the irony of raging against a ‘genocide’ while calling for the erasure of a people — all while our own incompetent, venal, self-absorbed political class insist in their mindless chatter on confirming every claim of our enemies for sheer, bald egomania.

I’m sick of it all. I know you’re all sick of it too.

And that, in a nutshell, is what I think about this.

Just because they’re lying, just because a vast perfidious campaign has overwhelmed global elites in a bid to clear the way for our removal, just because they’re still, after two millennia, building their visions of redemption on The Evil Jew — doesn’t mean there isn’t also, separately, a problem on the ground.

So what do we do now? Simple. We see it, we acknowledge it’s happening, we bring our rage to our inept leaders until they bend to our will and act to stop the breakdown…

And we soldier on.

We soldier on because the enemy really is coming to murder us. Because Hamas must still go if Gaza is ever to rise to a new day. Because Hezbollah will yet destroy Lebanon on the altar of destroying us. Because the ayatollahs built their whole damn religion on the extermination of our children.

We fix the broken things within us as if the pogromists and their simpering Kristofs don’t exist. We owe no answers to the propagandists who seek to clear a path to our deaths. But we do owe answers to ourselves.

Let the screaming mob rage and churn like so much sea-foam. Despite that raging mob, despite the enemy who still seeks our destruction, and yes, despite feckless incompetents like Ben Gvir, our minister of prisons, who claim to lead us — we remain the strongest, freest Jews who ever lived, more capable and committed than our self-destructive enemies ever imagined. And the task is still before us, yet to be completed, the sacred duty given to our generation to ensure our children don’t have to face the genocidaires who now surround us. We do not waver, we do not stumble. We soldier on.

Because fuck them all.

---

Inspired by Haviv’s energy, I’m leaving the comments on this post turned off. Why? Because outside the dog-rape libel, I was having a pretty good week! On Monday I visited Quantinuum in Colorado and got a personal tour of Helios 1, considered the all-around most powerful quantum computer on earth at the moment. Now I’m visiting Stony Brook University, where I’ll give two talks and meet lots of interesting people. Then I’m headed to NYC for the annual meeting of Quanta magazine’s advisory board.

Right now, then, I have neither the time nor the inclination to battle the infinite army of brain-eaten zombies who arrive for every single post touching on Israel. My life will be better this way.

WHOA … I’ve won the inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science! This has a particular meaning for me as someone who knew Luca Trevisan as well as I did for 25 years — who had him as a professor and thesis committee member, whose blog bounced off his blog, who benefitted tremendously from his expository work in TCS — before Luca tragically succumbed to cancer two years ago.

As I told the committee, receiving this award makes me want to use my blog for more actual CS theory exposition, and less venting, in order to retrospectively become worthier of such an honor.

I’m ridiculously grateful to the entire TCS community — my people, my homies — for tolerating me to do what I do.

If you’re curious, here’s the official citation:

The inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science is awarded to Scott Aaronson for his sustained and high-impact inspirational efforts to explain and promote our field to broad audiences. His blog Shtetl-Optimized has hosted remarkably frequent and elaborate posts over more than two decades, and has become a central meeting place for wide-ranging conversations across the TCS and Physics communities. Scott Aaronson’s blog posts contain crystal-clear, informative expositions of exciting new results, calibrated evaluations of technological claims, and profound analyses of topics in these fields and (way) beyond. The uniquely enthusiastic and witty style of his writings (including his book Quantum Computing Since Democritus and his other lecture notes and surveys), lectures, and interviews have made him a top invitee for both popular and professional appearances, attracting large audiences. These qualities have inspired many students to enter the field, and made Scott Aaronson a go-to person for journalists and scientists alike looking for a definitive word on the latest scientific activity in TCS and quantum computing.

---

In the rest of this post, I’m going to start practicing what I preached—y’know, about turning over more of this blog to actual exposition, of a kind that the Trevisan Award could plausibly be meant to encourage. I’ll start with something that’s been on my back burner for the past couple months: namely, the (lightly edited) transcript of a talk that I gave this spring at UT Austin’s undergraduate math club. So, without further ado, and in memory of Luca…

---

On the Decimal Digits of Powers of 2
by Scott Aaronson

Hi! I’ve given six previous talks here at UT’s math club, some on relatively “important” topics—Gödel’s Theorem, time travel, Huang’s proof of the Sensitivity Conjecture, and so on.

Today, I want to talk about an unimportant question, one that my son Daniel, who was then 8, and who’s sitting here in the front row (along with his sister Lily), asked me a few months ago.

Daniel asked: which powers of 2 can you double without needing to carry digits? Clearly 1, 2, 4, 32, and 1024 all have this property, their doubles being 2, 4, 8, 64, and 2048 respectively. Are there any others?

Since I happen to have the powers of 2 up to 2²⁰ = 1,048,576 committed to memory since childhood, I confirmed that there were no other examples up to there: 128, 256, 512, 2048, etc. all require carries. So I told Daniel: I can’t find any other example, and on that basis, I conjecture that there aren’t any more. But if that conjecture is true, I don’t know if it will ever be proven, by humans or even AI!

Then I googled it, and saw that this is a known question (not very well known, but there’s a StackExchange post about it). And indeed it had been checked up to 2^millions, and no other counterexample had been found.

---

Why did I become confident so quickly that yes, 1024 is probably the last example of a power of 2 that can be doubled without carrying?

Because of the heuristic that the decimal digits of 2ⁿ are more or less “random,” apart from various constraints that are irrelevant here (like that the last digit always cycles among 2, 4, 6, and 8). And 2ⁿ has about n/log₂10 decimal digits. Since only 0, 1, 2, 3, 4 can be doubled without carrying, the probability of 2ⁿ being a counterexample should therefore be about $$ (\frac{1}{2} )^{n / \log_2 10}. $$

So, if we’ve already checked up to (say) n=1000, then the probability of a larger counterexample should be at most

$$ \sum_{n=1001}^{\infty} (\frac{1}{2} )^{n / \log_2 10} $$

which, when we sum the geometric series, is exceedingly close to 0.

---

Ah, but why did I say that I don’t know if the conjecture will ever be proven? Because it seems to belong a large class of similar statements, none of which mathematicians have had any idea how to prove.

Variant of a conjecture by Jeffrey Shallit: 65,536 is the only power of 2 that has no power of 2 among its decimal digits.

Freeman Dyson’s conjecture (2005): There’s no power of 2 for which, when you reverse the decimal digits, you get a power of 5.

Paul Erdös’s conjecture (1979): For every n≥9, there’s at least one ‘2’ in the base-3 representation of 2ⁿ.

Or looking even more broadly:

Conjecture: The decimal expansion of π is not all 6’s and 7’s after some finite point.

(This would follow from the stronger conjecture that π is base-10 normal—that is, that every finite pattern of decimal digits occurs in it with the limiting frequency you’d expect.)

Or:

Conjecture: π+e is an irrational number.

What all the above conjectures have in common, and what I find so fascinating about them, is that they seem hopeless to prove for exactly the same reason why they seem almost certainly true. Namely, they all seem to be true “merely” because it would be too insane of a coincidence were they false!

The trouble is, that’s not the sort of reason that seems amenable to turning into a proof. Fermat’s Last Theorem is an interesting exception that proves the rule here. That xⁿ+yⁿ=zⁿ has no nontrivial integer solution for n≥3, did seem almost certainly true on statistical grounds for n≥4 (and for the n=3 case, a proof goes back to Euler). And of course, FLT was ultimately provable. But Wiles’s eventual proof exploited a lucky connection between the Fermat equation and deep, fancy things like modular forms and elliptic curves. At no point did the proof formalize the statistical argument that a 12-year-old could understand, for why the theorem is “almost certainly true.” It simply had nothing to do with the statistical argument.

So then, if you wanted to prove conjectures like my son Daniel’s, or like Shallit’s or Dyson’s or Erdös’s above, the question would be: could these “recreational” problems about base-10 representations ever be connected to anything similarly deep? Right now, it’s very hard to see how they could.

Still, all hope is not lost! Here’s a striking theorem that I learned about when I researched this:

Theorem (James Maynard, 2016): For every digit a from 0 to 9, there are infinitely many primes with no a’s in their base-10 representation.

The proof uses heavy Fourier-analytic techniques. Likewise, presumably there are infinitely many primes that you can double without carrying—2, 3, 11, 13, 23, 31, …—because the primes are much denser than the powers of 2! And presumably there are infinitely many primes that are missing any two decimal digits, or even whose decimal digits consist entirely of 0’s and 1’s. But Maynard’s techniques are not yet powerful enough to prove such things.

---

Even though I promised a topic of no importance today, I can’t resist pointing out a potential connection here to one of the biggest questions on earth right now, and something that’s professionally interested me for the past four years: namely, the question of how to align powerful AIs with human values and prevent them from destroying the world.

Paul Christiano, and the Alignment Research Center in Berkeley that he founded, have developed a whole program for how to make AI safe that depends on the possibility of formalizing “heuristic arguments”—that is, the kinds of arguments that convince us that the above conjectures are all almost certainly true, even without proofs of them.

The intuition here is that we’ll never have a rigorous proof that, for example, a real-world neural network will behave safely under all circumstances—it’s just too complicated. The best we can hope for is an argument that, e.g., “for this model to scheme against humans would require a crazy unexplained coincidence in its weights.” But how can we hope to formalize such arguments? As baby test cases, can we at least formalize our intuitions for why π is normal, or why Daniel’s conjecture is true, in some principled way?

ARC has tried: there’s a 2022 paper by Christiano, Neyman, and Xu on “Formalizing the presumption of independence.” But it’s tricky, and ARC itself would be the first to agree that the existing results are unsatisfying. How do we even formalize the intuition that, for example, you should be willing to bet at even odds against the 10¹⁰⁰th digit of π being a 5?

---

In the rest of this talk, I’d like to circle back to Daniel’s original question about powers of 2, and show you some things that can be proved about it—with thanks to Greg Kuperberg and my other friends on Facebook, and in some cases to GPT5Pro.

Let’s start with the following easier question. Is there a power of 2 whose decimal digits start with 31415? Or with the complete works of Shakespeare, encoded by letter values in some suitable way? Or with a googolplex digits all of which can be doubled without carrying (as Daniel wanted)?

I claim that the answers are yes, yes, and yes! How do we prove this?

The key fact we’ll use is simply that log₁₀2 is an irrational number. (If you don’t remember the proof: suppose log₁₀2 = a/b. Then 10^a/b = 2, so 10^a=2^b. But this has no integer solutions other than a=b=0.)

Suppose we want k as a prefix, where 10^d-1 ≤ k ≤ 10^d. Then we want integers n,r such that

$$ k 10^r \le 2^n \le (k+1) 10^r, $$

i.e. taking the base-10 log,

$$ \log_{10}k + r \le n \log_{10}2 \le \log_{10}(k+1) + r. $$

In other words, the fractional part of n log₁₀2 needs to lie between the fractional part of log₁₀(k), and the fractional part of log₁₀(k+1) (where again, k is given).

But now we can appeal to the following Key Fact: if α is any irrational number, then the set

{the fractional part of nα : n∈N}

is dense in the interval [0,1]. Or equivalently, if I rotate around and around the unit circle by 2απ radians each time, then if α is irrational, I’ll eventually get arbitrarily close to any given point on the unit circle.

Why is the key fact true? Just the pigeonhole principle! Clearly, for any ε>0, the fact that α is irrational means that there must be two points, xα and yα, whose fractional parts are distinct yet closer together than ε. But then, by adding multiples of (x-y)α, we can get our fractional part to be ε-close to anything in [0,1].

And to sum up, this is why there must be a power of 2 whose decimal representation starts with the complete works of Shakespeare, or with a googolplex carry-free digits! (Indeed, from the above discussion, we could even extract an efficient algorithm for constructing that power of 2.)

---

So much for the first decimal digits of 2ⁿ. Now let’s look at 2ⁿ‘s last decimal digits!

Here there are some complications, arising from the twin facts that

(a) 10 is composite, and
(b) 2 is one of its factors.

But we can deal with those complications!

For starters: what are the possible last decimal digits of 2ⁿ?

1, 2, 4, 8, 6, 2, 4, 8, 6, …

So, there’s an initial 1, but then we cycle forever through the even nonzero digits.

What about the last two digits of 2ⁿ? If you’ve never tried this before, it’s instructive to work it out:

01, 02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04, …

So, there’s an initial 01 and 02, but after that, we cycle forever through 20=4×5 possibilities, namely all the possible multiples of 4 whose last digits are nonzero.

You can check that the general pattern is: the last k decimal digits of 2ⁿ have an initial segment that looks like 001, 002, 004, 008, …, 2^k-1. And then there’s an eternal cycle of length 4×5^k-1, where the last digit can be any of 2,4,6,8, while every other digit can either be any possible even digit or any possible odd digit, depending on the digits to its right—in (if you want to say this a fancier way) a recursively defined embedding of the powers of 2 mod 5^k into the cyclic group Z/10^k. So, there’s an initial “runup” as you fill out all the needed powers of 2, but then once that’s done, you just cycle around forever in an embedding of Z/5^k into Z/10^k, because

(a) 2 happens to be a primitive element of Z/5^k for any k, and
(b) 5 divides 10.

So in particular, and relevant to Daniel’s conjecture: there exists a power of 2 whose last googolplex digits can all be doubled without carrying. Why? For the last digit, you can pick 2 or 4. Then, for the last googolplex digits but one, you can pick 1 or 3 for those constrained to be odd, and 0, 2, or 4 for those constrained to be even. Lots of choices that work!

---

So, we can avoid carries in the leftmost digits of 2ⁿ, we can avoid carries in the rightmost digits … so that “merely” leaves all the digits in the middle, where who the hell knows! Empirically, the digits seem to pass every standard randomness test that you can throw at them. So in particular, e.g., the fraction of the digits that are in {0,1,2,3,4} seems to converge inexorably towards 50%, so that it’s extremely plausible to conjecture that the fraction is less than 49% or more than 51% for only finitely many values of n. But of course, that’s presumably even harder to prove than Daniel’s original conjecture.

---

OK, last topic. Suppose we want to program a computer to check Daniel’s conjecture up to 2ⁿ, for some huge n. What algorithm will do that most efficiently? A naive algorithm would just calculate 1, 2, 4, …, 2ⁿ and check all the digits of all of them. That takes O(n²) time, since each 2^k, for k=0,1,…,n, has ~klog₁₀2 = O(k) decimal digits.

We can improve this to roughly O(n) time, by simply noticing that we only need to check O(1) digits per power of 2 in expectation, presumably, until we find the first digit that requires carrying. Then we don’t even need to compute the remaining digits: we can simply move on to the next power of 2. (This sort of trick is used all over the place in the design of fast algorithms.)

But when I posted about Daniel’s problem on Facebook, my friend Greg Kuperberg (who’s a mathematician at UC Davis) noticed that further improvements are possible. To wit: 8×6 = 48, which again ends in 8. So, 8×16 ends in 8, as does 8×16^k for every k≥0. Meaning: no 2ⁿ where n=3+4k can possibly be a counterexample to Daniel’s conjecture. They’re all ruled out!

Likewise, 64×1,048,576 ends in 64, so no 2ⁿ of the form n=6+20k can be a counterexample. They’re all ruled out as well.

We can keep going this way, filling out the “search tree” of potential counterexamples to Daniel’s conjecture via breadth-first search. At the root of the search tree, we try all possibilities for the last digit. One level deeper, we try all possibilities for the second-to-last digit, and so on. As we go, we prune subtrees according to constraints like the ones above that we keep discovering and adding.

When I worked this out, I got an algorithm for checking Daniel’s conjecture up to 2ⁿ, which under reasonable assumptions takes time only O(n^α), where α = 1-log₅2 ≈ 0.569, and space only polylog(n).

Paul Crowley (who’s my Facebook friend) then actually implemented this algorithm, and he tells me that he used it to check that Daniel’s conjecture holds all the way up to $$2^{10^{21}}$$ (!!), using 40 minutes on a 128-core machine.

So, to return at last to the first thing I told Daniel: yes, I think his conjecture is almost certainly true, even though I have no idea when, if ever, the human race or its successors will have a proof.