Shtetl-Optimized

Enjoy all three hours of this! Dana covers what the Unique Games problem is, the structure of a proof of its NP-hardness, exactly where the previous attempts to complete the proof (based on the Long Code and the Hadamard Code) got stuck, what new tree-based code the AI discovered, and how the new code gets around the Long Code and Hadamard Code’s limitations. She doesn’t get to the soundness analysis.

Feel free to ask questions in the comments. I might write some notes here later with my own doofus understanding of Dana’s talk. Experts are of course hard at work on more formal writeups of the proof (which will hopefully be more comprehensible than the AI’s writeup).

The “For Dummies” Version (apologies for not including this earlier):

• Yes, an AI solved a big open problem about quantum computing
• No, this doesn’t kill quantum supremacy, or change how we build quantum computers, or whatever else you read on Twitter
• What it does, is to rule out a potential class of quantum speedups that most of us didn’t believe would exist anyway (namely, those that would compute a yes-or-no property of exponentially many random bits, superpolynomially faster than any classical algorithm)
• It means my prediction was right, so you should listen to me more in the future!

---

We now, of course, live in age where longstanding open problems in quantum computing theory (and all theoretical computer science, and all math) are dropping like flies, to the extent that there’s no way I could possibly do a post on each and every bombshell. But I can’t exactly avoid the Aaronson-Ambainis Conjecture, given that my name is on it, and that I cared about the answer to this one (back in 2019, I even blogged about an attempted solution that ultimately turned out to be fallacious).

For those tuning in from home, the AA Conjecture, which Andris and I posed back in 2009, says that every degree-d polynomial p:{0,1}ⁿ→[0,1] in n Boolean variables, with constant variance, has some variable whose influence is at least 1/poly(d). The reason Andris and I cared about this conjecture is that, as we proved, it implies that there’s no superpolynomial advantage of quantum query complexity over classical query complexity for decision problems that works on most Boolean inputs. Or, in terms of complexity classes, that there’s no hope of separating P from BQP relative to a random oracle, without proving P≠BQP or something of the kind in the unrelativized world. This would finally answer a question of Fortnow and Rogers from 1998.

The connection between quantum algorithms and polynomials came from the famous 1998 paper of Beals et al., which showed that, if Q is a quantum algorithm that makes T queries to an oracle X, then Pr[Q(X) accepts] can be written as a multivariate real polynomial p(X) in the bits of X, of degree at most 2T. The proof of my and Andris’s result is then simply this: take the polynomial p, find in it a variable of influence at least 1/poly(T), and query that variable, and keep repeating until there’s no longer such an influential variable—at which point, by assumption, p is nearly a constant polynomial, which means you’ve learned whether Q accepts with high probability over X. This provides a classical simulation of the quantum algorithm Q—a simulation that makes poly(T) queries to the oracle X and that works for most X’s.

The AA Conjecture caught on to an extent Andris and I couldn’t have predicted. Some who worked on it barely even cared about the implication for quantum computing, and just wanted to solve the problem about polynomials! There were, I’m both proud and sorry to report, Fourier analysis experts and grad students who oriented their whole research programs around trying to prove AA, with lots of proofs of special cases, some of them very recent. A proof of full AA was one of the last remaining open problems in quantum query complexity that everyone seemed to agree was centrally important. I was surprised, honestly, to see it missing from OpenAI’s Mathocalypse dump a few weeks ago. Surely they tried it, so was it really so much harder than all the problems that were solved?

---

Now a startup called Physical Superintelligence has announced a proof of the AA Conjecture, specifically showing that there’s a variable of influence at least ~1/d⁶, which they say they obtained using their proprietary research harness on an internal Claude model. (What role the harness played, compared to the internal model, is something I don’t know.) The effort was led by David Turturean and Jim Halverson at PSI. They actually let me know about this several weeks ago, but I had to keep it secret until the announcement late last week.

I haven’t yet understood the proof, although I hope to. In the meantime, though, I believe the proof is correct for two reasons. Firstly, there’s a Lean certificate, and secondly, human experts (I’m no longer an expert on my own conjecture!) have already gone over it and understood it. In fact, there’s already a beautiful-looking exposition written by Guy Blanc of MIT and Jordan Docter, Carmen Strassle, and Li-Yang Tan of Stanford, which looks like a perfect starting point for those seeking to go much deeper. Or, for those seeking to go only slightly deeper, PSI’s blog post on the advance is sufficiently well-written that it saves me from the need to write too much more here.

Alas, as reported by Ashley Montanaro, there were the usual forehead-banging misconceptions about what this result means for quantum computing. So for example, Pedro Domingos of U. of Washington blasted out to his 137,000 X followers that the proof means that “the dream of quantum supremacy is dead.” The truth, as Pedro knows perfectly well (or easily could know), is that it rules out one particular type of quantum supremacy (namely, for yes-or-no problems relative to random oracles) that we’d already conjectured didn’t exist anyway. It doesn’t undermine any form of quantum supremacy that we did conjecture to exist! It has zero effect, for example, on Shor’s factoring algorithm, which uses a highly non-random (periodic) oracle for the key internal step. It has zero effect on the simulation of quantum physics and chemistry, which generally doesn’t depend on oracle algorithms at all. Even just relative to random oracles, the Yamakawa-Zhandry breakthrough from 2022 dramatically underscored that, if we switch our attention from decision problems to other kind of problems (in Yamakawa and Zhandry’s case, to NP search problems), then exponential quantum speedups do become possible. Anyway, this was sufficiently intellectually dishonest on Pedro’s part that it makes me disinclined to take him seriously about anything ever again [ADDED: I appreciate that Pedro has now posted a partial correction, saying “or maybe not”].

But, OK, given how radically new it is to have an AI solve so many of our longstanding open problems, I suppose “people are wildly misinterpreting a QC advance on social media” is an almost comfortingly familiar problem to have!

If you’re wondering how I feel about the proof of AA—well, much like my wife Dana with the Unique Games Conjecture, it’s many different emotions at once.

• Satisfied that our conjecture turned out to be true after all (it’s nice to be 100% right about something from time to time!)
• Awestruck by the new reality of the world in which we live in
• Disappointed that humans didn’t get to snag this conjecture before the robots did (with some more years, I think it’s very likely that they would have)
• Fatigued by the endless wonders from Aladdin’s Cave, the neverending buffet of solutions to longstanding open problems, wondering when if ever we’ll have time to digest it all

Anyway, huge congratulations to David Turturean and Jim Halverson, to Physical Superintelligence, and of course to Claude on this achievement!

As everyone knows, this week was a (an?) historic one for the State of Texas and for the United States as a whole—because this is the week when my wife Dana finally gave a 3-hour public lecture on OpenAI’s recent proof of the Unique Games Conjecture! Thanks so much to the nearly 200 people who joined us in person or via Zoom, and to the staff of UT Austin’s CS department for pulling the event together on short notice. Video will be up on YouTube as soon as we can manage it.

---

But also, yes, there was an election.

I remember that, when Dana and I moved to Texas in the summer of 2016, we were excited to be a small part of what seemed at the time like Texas’s impending transformation into a cosmopolitan blue state.

And now the prophecy is finally being fulfilled. But so many strange and harrowing things have happened in the interim, that I feel like Murph when her father finally returns to her at the end of the movie Interstellar.

---

So it turns out that, indeed, the Democrats could’ve easily recaptured both houses of Congress without any need to sell their souls to the likes of Hasan Piker or Abdul El-Sayed. And now the keffiyeh-clad revolutionaries will claim a mandate directly from the people, to put to the sword all the evil landlords and techbros and kulaks and bourgeoisie and (obviously) Zionists, and thereby finally usher in the utopia that failed the first 10,000 times it was tried. I see them as more likely to inspire a Republican comeback in 2028 (as unlikely as it seems this week) than to achieve their stated goals.

For please remember that the socialist firebrands massively underperformed more moderate Democrats on Tuesday—it looks like the socialists were merely lifted up by the same tide of justified anti-MAGA rage. Yes, in the US and across the Western world, some university humanities departments continue to churn out young people who’d see my family’s slaughter as an inspiring (or at least deeply understandable) act of revolutionary justice, and who vote on that basis. By and large, though, the American voters simply belatedly realized that Trump is a charlatan who was never going to deliver anything he promised, and also they wanted cheaper gas.

---

The Allied victory over Nazi Germany was glorious, it called for parades and dancing in the street, and it was 3,000% earned by Nazi behavior if anything in human history ever was. It left only one tiny problem for the future—namely that, within the winning coalition, the fans of liberal democracy, science, and Enlightenment still needed to confront the Stalinists, whose evil rivaled even the Nazis’, yet who believed their fanatical ideology to be the one vindicated by events. Why was I so often thinking about that these past couple days?

---

There was, of course, also a big election in Israel. Given the results, I pray that Gadi Eisenkot finds some way to form a coalition, or at least soft coalition, with Israel’s Arab parties, since that’s clearly what it will now take finally to topple Netanyahu, a man whose corruption (like Trump’s or Ken Paxton’s) knows no bounds. I’m under no illusions that this step would do anything to appease the hundreds of millions of protesters around the world whose true demand (as they’ll explain if you ask them) never had anything to do with Israeli policies or Gaza or the West Bank or Bibi Netanyahu, but was always simply that Israel cease to exist—that Israel’s Jews either “go back to Poland” or the other countries where their grandparents were murdered or expelled, or preferably just die, as on October 7.

Nevertheless, I pray for a coalition of moderate Israeli Jews and Arabs, firstly because it’s morally right, secondly because it’s politically expedient, and thirdly because it will impress on at least some fair-minded observers the enormity of the moral chasm here—that, whereas the Arab countries expelled or murdered virtually all of their Jews, the State of Israel not only tolerates its Arab minority but gives it the right to vote and to wield power.

Whatever else one can say, Israel’s Arabs have been sufficiently loyal to their nation that, on October 7, Hamas murdered them right along with the Jews, treating them as Zionist collaborators and traitors to Islam. I’d like to see that loyalty rewarded with a role in Israel’s governing coalition.

---

As is becoming standard practice with my political posts, I’m closing the comments—because life is short, and these days, the overwhelming majority of comments that I get on posts like this one, whichever ideological axe they’re grinding, are not ones that engender in me even minimal respect for their authors. I apologize to those who would’ve actually pursued a thoughtful dialogue with me or others had I left the comments open—to all five of you, or however many righteous men of Sodom there might be.

Boooooo! What spooooky times we now live in, with AI rapidly advancing in capabilities and solving more and more major open math problems!

So it seems like a perfect occasion to share yet another podcast. I know I’ve been dropping them like every day, but this is a special one, with Brian Greene for his World Science Festival, recorded in-person when I visited Columbia University a week ago. Note that we don’t talk about OpenAI’s refutation of the Exponential Time Hypothesis because the announcement of that was still two days in the future!

---

Bonus Addition From Just This Morning (Nov. 3): Another podcast, about quantum computing, foundations of quantum mechanics, AI, consciousness, and I forget what else … this one with writer Robert Wright, whose book The Moral Animal made a huge impression on me back when I was 13 years old!

In my “Mathocalypse” post, I mentioned that my wife Dana—who’s been working on Subhash Khot’s Unique Games Conjecture since ~2009, for the entire time I’ve known her—has for the past few weeks (while on sabbatical at the Simons Institute in Berkeley) been spending essentially all of her time laboring to understand OpenAI’s recent proof of the conjecture. Having now studied the proof closely in collaboration with Subhash Khot himself, Johan Håstad, Dor Minzer, and other colleagues, and (naturally) GPT-6 Astra, Dana probably now understands this crown jewel of OpenAI’s release as well as anyone does. This week, she gave two well-received whiteboard talks on the proof at Simons Institute. So, I and others encouraged her to give the same talks next week at UT Austin when she’s back here, and Dana agreed! Because of the large timely interest, we’re going to do a live Zoom option, and will also record the talk for later sharing on YouTube. Please note: While all are welcome, this is a 2-hour technical talk. The first hour will review key ideas from hardness of approximation, while the second hour will describe the new construction. —SA

---

Title: The Unique Games Conjecture – Proved (!!?)

Speaker: Dana Moshkovitz (UT Austin)

When: Wednesday Nov. 4, 3:30-5:30pm US Central (with a brief break in the middle)

Where: UT Austin, Gates Dell Complex 6.302. Live Zoom will be available here, and a recording will be available later.

Abstract: The Unique Games Conjecture of Khot says that it is NP-hard, given a system of linear equations of the form x_i-x_j=b_ij (mod p) over variables x₁…x_n, where 99% fraction of the equations can be satisfied, to find an assignment satisfying 1% of the equations (here p is a sufficiently large constant).

This conjecture implies optimal inapproximability results for many optimization problems. 

A few weeks ago OpenAI released a writeup with a proof of the Unique Games Conjecture, as well as a Lean formalization of the proof. The writeup, like others released that day, is not written in a way that’s especially readable to human mathematicians. 

My goal in this talk is to offer my mental map of the proof, in a way that’s helpful to theoretical computer scientists who are familiar with the area. I think of the innovation as a new code construction, “Hadamard with a noise test.” I’ll sketch how it fits into the NP-hardness reduction. Then I’ll describe the code construction fully and sketch its soundness analysis.    

I’ll also point out a couple of ingredients of the proof that are of independent interest, like a simple quadratic that behaves “like a linear,” and a probability bound using a trick with harmonic numbers.

As always, I strongly recommend 2x speed, which compensates somewhat for my verbal infelicities!

---

New! More podcasts keep dropping! This one is with the AI alignment researcher Roman Yampolskiy, about … well, AI alignment, plus the Mathocalypse, plus quantum computing, plus whether the universe is a simulation, and I forget what else! Man do the YouTube comments make me despair of humanity though.

---

Another one that recently dropped, with Sophia Aryan:

---

With Curt Jaimungal:

The title Curt put next to my head could’ve been in reference to many, many things! But sorry, he just mean AI. He and I start with the Mathacre, of course, but then we get onto the firewall paradox and then Curt starts asking about computational complexity and the Second Law, and then about Integrated Information Theory.

---

Ah, and another one that just dropped! Man’s Search for Meaning podcast (recorded in-person in Austin), with Yannick Bernard, who asked me about quantum computing, AI, my personal story, grade-skipping, antisemitism, and I don’t even remember what else. I didn’t refuse to answer anything. (Note: this one was recorded over the summer, which is why I so weirdly omit the latest AI math breakthroughs!)

---

OK, despite the title of this post, short break from “The Topic.” Here’s an absolute masterpiece of mathematical exposition, from the “Polylog” YouTube channel, which tells the story of the determination of Busy Beaver values through spectacular animations. I play cameo roles in the video, although I embarrass myself (as the video silently points out) by transposing two digits in the value of BB(5)…!

---

Just for old times’ sake, a short podcast about quantum computing with Danny Li.

---

And, coming soon (not on YouTube quite yet): a conversation about the Mathacre with celebrated physics popularizer (and character on The Big Bang Theory) Brian Greene, recorded in-person in NYC during my recent trip to speak in the math department at Columbia University!

---

And to preempt the inevitable comments about it: yes, my students just came to my office to tell me that an OpenAI model has now refuted the Exponential Time Hypothesis, by giving an algorithm to solve 3SAT in an amount of time that scales roughly like exp(n/√log(n)). Even as we struggle to digest the previous courses, the endless buffet continues!

Someone writing an article for the Israeli press about “people abroad who love Israel but might be worried” emailed me the following questions:

“1. What is something about Israel that you admire/appreciate over the years?

2. What are you worried the most about Israel these days?”

So I replied as follows:

“It’s hard to know where to start with either of your questions! But briefly:

Tiny Israel standing up for itself, against an often hostile and unjust world, is a huge part of what’s given me the self-confidence to stand up for myself in my own life. That was true even before I had visited Israel or spent significant time there, gazed across the desert at the still-clear ruins of the Roman siege of Masada, staggered overwhelmed out of Yad Vashem into the sunlight of Jerusalem, tasted the hummus or pomegranate juice or ice cream with blended fruit, befriended or had academic collaborations with dozens of Israelis, or married an Israeli woman.

My fear is merely the ‘obvious’ one — that, in response to the staggering hostility directed against the ‘Jew among the nations,’ Israel will become more and more belligerent, isolated, and right-wing. It will get demographically overwhelmed by those who don’t want to work or serve in the army, while hundreds of thousands of secular educated Israelis leave. It will be internally divided almost to the point of civil war. It will repudiate the liberal-democratic vision of Herzl and Ben-Gurion, of world-class universities and making the deserts bloom, for the swaggering, theocratic vision of Smotrich and Ben-Gvir, of chasing Palestinians from their olive groves. It will become more and more like the hateful caricature of itself that the anti-Israel people in the West always imagined. And then, having been internally weakened in all of these ways, it will finally be destroyed by its external enemies, who will never have rested the whole time, who never once wavered in their dream of a second Holocaust.

I hope and pray that in the upcoming election, the Israeli voters make optimistic choices that repudiate these fears.”

---

As I’ll do more and more with political posts, I’m leaving the comments off. Why? Because my remaining life is too short to spend it battling an endless parade of trolls and griefers, leftists and rightists and just nihilists, who might or might not be AI.

Today, I take a break from your regularly-scheduled AI mathocalypse programming to urge my American readers to vote in the Congressional midterms, early if possible, if you haven’t already. Especially if your state faces one or more major contests, as does my adopted home state of Texas.

Me, I voted straight-ticket Democrat today, as I’ve done in every election since I became eligible over a quarter-century ago (except for when I vote-swapped with someone from another state).

So yes, I voted for the guy who studied theology a short walk from my house, and who seems to have really internalized the whole Jesus thing about kindness to everyone—

—over his sneering, thuggish, cartoonishly mafia-like opponent. Fingers crossed that Talarico pulls off a historic upset for our state (he’s currently a 2-to-1 favorite in the prediction markets).

The Texas Republicans did everything they possibly could to make this choice easy for me, by being corrupt, conspiratorial, racist, and Taliban-like even by the jaw-droppingly debased standards of MAGA in 2026. As I draw breath, I could never vote for a slate one of whose candidates attacked UT students for the crime of being visibly Southeast Asian while cheering their school’s football victory from the stands—and whose other candidates could barely bring themselves to condemn this knuckle-dragging racist, for fear of angering their base. (It’s like, didn’t you want immigrants to assimilate to American culture? What more could these kids possibly do, short of skin bleach?)

All the same, this was also the first US election in my lifetime where I felt like my vote was genuinely in play—especially when I listened to Talarico’s condemnations of Israel, for having the temerity to fight the same kind of war any random other nation would’ve fought had it been attacked as Israel was on October 7. When Hasan Piker came to speak to a cheering crowd here at UT Austin, I actually wrote to someone I know in the Talarico campaign, to ask whether Talarico would show enough balls to condemn Piker’s many antisemitic and anti-American statements, and renounce his support. My contact was nice enough to reply to me, saying: don’t worry, James is taking care to be far away from Austin during Piker’s visit, so he won’t need to engage at all!

So then, this is my candidate: the guy who’s strategically silent on the wildly-popular streamer who’d gladly see my Israeli family members raped and beheaded, rather than campaigning with that streamer like Abdul El-Sayed did in Michigan. I unironically believe that, for Talarico, it took genuine moral courage to resist the whole momentum of his party’s youth even to this extent.

To earn my vote in the near future under these circumstances, all a Texas Republican would need to do is be somewhat sane or reasonable. He or she might affirm, for example, that racism is bad, that abortion is a woman’s choice, that Christianity is not the state religion of the US, that Covid vaccines work, that human emissions are worryingly changing the earth’s climate, and/or that Joe Biden won in 2020, while still being arbitrarily right-wing on taxes and other stuff. He or she could then simply wait for the Democrats to descend fully into the worldview of the masked hooligans who are currently setting France’s beautiful cities aflame, terrorizing its shopkeepers, and looting as many Louis Vuitton handbags as they can carry … all for Palestine, of course, and for the death of global capitalism, and for the violent overthrow of the scheming, money-grubbing, hook-nosed, international Talmudic … err, I mean “Zionists.”

What I’m trying to say is, it was a genuine achievement on the part of the Texas Republicans to fail to earn a single vote from me this cycle.

As I announced on this blog a couple weeks ago, I’m teaching a new course this semester at UT Austin, entitled AI Alignment Theory. To call such a course “timely” seems like an understatement; this is the first course I’ve ever taught for which multiple gargantuan developments relevant to the course have happened while I was teaching it.

Since AI alignment is still a field with no standard textbook (although that might be changing), no accepted body of mathematical theory, etc. etc., the way we’ve been running the course is like a humanities discussion seminar, albeit one that happens to be in a CS department and to include technical results from time to time. Basically, in each class session, a student “rapporteur” gives a talk on an AI alignment reading—which include “ancient” readings (from way back in 2016), “modern” readings (from, say, last week), and everything in between—and then we freely discuss and debate whatever was presented, with my own role mostly limited to that of gadfly (occasionally I’ll do a mini-lecture on some technical concept).

Anyway, two weeks ago, I promised a list of the papers and other writings that we’ve been discussing, as well as student “rapporteur reports” on those papers, which cover not only the papers themselves, but the students’ thoughts about the papers and (anonymized) summaries of points raised during our class discussion. People have been bugging me for that ever since.

Since I am to please, here you are, without further ado! I’ll continue to update the list as the semester progresses, so that this post can serve as a central public repository for the course.

[By popular request — Course Syllabus]

1. AGI Ruin: A List of Lethalities, by Eliezer Yudkowsky (2022). Rapporteur report by Tennyson Bardwell (this is the one that we posted previously).
   
2. Concrete Problems in AI Safety, by Amodei, Olah, Steinhardt, Christiano, Schulman, and Mané (2016). Rapporteur report by Daniela Wiepert.
   
3. The Alignment Problem from a Deep Learning Perspective, by Ngo, Chan, and Mindermann (many versions but latest is 2025), and Research Priorities for Robust and Beneficial Artificial Intelligence by Russell, Dewey, and Tegmark (2016). Rapporteur report by Oleg Pittman and Jack Holt.
   
4. What Happened: OpenAI and HuggingFace, by Zvi Mowshowitz; The Rise and Fall of Agent Civilizations, by Dwarkesh Patel, and the METR report by on the HuggingFace incident, by Greenblatt, Cotra, and Wijk (all 2026). Rapporteur report by Shourjo Aditya Chaudhuri and John Robertson.
   
5. We Must Pace the Frontier, by Dario Amodei (2026). Rapporteur report by Dhilan Shah.
   
6. The Basic AI Drives, by Stephen Omohundro (2008), and Optimal Policies Tend to Seek Power, by Turner, Smith, Shah, Critch, and Tadepalli (2023). Rapporteur report by Bill Zheng.
   
7. Corrigibility, by Soares, Fallenstein, Yudkowsky, and Armstrong (2015). Rapporteur report by Sukrut Chikodikar.
   
8. The Off-Switch Game, by Hadfield-Menell, Dragan, Abbeel, and Russell (2017). Rapporteur report by Praneel Seth.
   
9. Planting Undetectable Backdoors in Machine Learning Models, by Goldwasser, Kim, Vaikuntanathan, and Zamir (latest version 2024), and Oblivious Defense in ML Models: Backdoor Removal without Detection, by Goldwasser, Shafer, Vafa, and Vaikuntanathan (2025). Rapporteur report by Agrim Jain and Indira Dutta.
   
10. Backdoor Defense, Learnability, and Obfuscation by Christiano, Hilton, Lecomte, and Zhu (2024), and Unelicitable Backdoors in Language Models via Cryptographic Transformer Circuits, by Draguns et al. (2024). Rapporteur report by John Dunbar.
    
11. Functional Decision Theory: A New Theory of Instrumental Rationality, by Eliezer Yudkowsky and Nate Soares (2018). Rapporteur report by Isaac Noel (coming).
    
12. Robust Cooperation In the Prisoner’s Dilemma: Program Equilibrium via Provability Logic, by Barasz, Christiano, Fallenstein, Herreshoff, LaVictoire, and Yudkowsky (latest version 2021). Rapporteur report by Shunan Zheng.
    
13. Sleeper Agents: Training Deceptive LLMs that Persist Through Safety Training, by Hubinger et al. (long list of authors) (2024). Rapporteur report by Anthony Wang (coming).
    
14. Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback, by Conitzer et al. (long list of authors) (2024) and Toward a Theory of Value in AI Alignment, by Ahmed, Birhane, Smart, Kay, Shrishak, and Tobin (2026). Rapporteur report by Priyanka Sadagopan.
    
15. Claude’s Constitution, by Amanda Askell, Joe Carlsmith, Chris Olah, Jared Kaplan, Holden Karnofsky, et al. (2026). Rapporteur report by Alan Li.
    
16. AI Safety via Debate, by Geoffrey Irving, Paul Christiano, and Dario Amodei (2018). Rapporteur report by Sampoorna Poria (coming).
    
17. Scalable AI Safety via Doubly-Efficient Debate, by Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras (2023). Rapporteur report by Aarushi Lakhi (coming).
    
18. AI as Normal Technology, by Arvind Narayanan and Sayash Kapoor (2025). Rapporteur report by Weixi Chen (coming).
    
19. On the Dangers of Stochastic Parrots, by Emily Bender, Timnit Gebru, Angelina McMillan-Major and Shmargaret Shmitchell (2021). Rapporteur report by George Tsoukalas (coming).

(More readings TBD, until the semester ends!)

Thanks to my TA, Lin Lin Lee, for her help in getting all of this together.

Update: I welcome elevated discussion of these papers and rapporteur reports in the comment section; some of the students might chime in too! Because of the connection to an academic class, though, in this post I’ll be especially ruthless in keeping out nonconstructive or off-topic comments.

“The Topic” being, of course, the Mathocalypse, except sometimes with AI alignment and even quantum computing and complexity theory and other stuff thrown in.

With Ryan Peterman:

Notably, near the end of the above podcast, you can watch my live reaction to the news that an Anthropic model found algorithms for the 3SUM and the All-Pairs-Shortest-Path problems beating records that stood for generations—news that hadn’t yet reached me when I woke up and logged in. (If you don’t feel like watching, my reaction is basically: “uh, wow … if I hadn’t been so overstuffed with delicacies right now from history’s biggest math breakthrough buffet, I’d surely be giving this one the individual amazement that it deserves…”)

And here’s with “Modern CTO”, on a similar set of topics:

Oh, and a third one: MTS podcast with Theo Jaffee.

Enjoy, and thanks to the hosts of these podcasts!

---

Update (Oct. 19): There’s been a rapid-fire recent sequence of AI-assisted improvements to my 2016 result with Adam Yedidia, showing that the 8000th Busy Beaver number eludes the axioms of set theory. I haven’t even kept track of all of them, but the very latest, by friend-of-the-blog Elliot Glazer, shows that the value of BB(230) is independent of ZFC (see here for explanation).