Ryan O'Donnell

A couple of my course lectures about ETH and SETH and related things: youtube.com/watch?v=dVQr... youtube.com/watch?v=NMOM... (From last week!) I will be the first to admit, I was repeatedly on the record as believing SETH :-)

William Hoza on the BPL=L result: www.youtube.com/watch?v=2hVv...

Ben Brubaker (@quantamagazine.org) on Yumou Fei, Dor Minzer and Shuo Wang's proof of 4-to-1 Conjecture: www.quantamagazine.org/as-ai-closed...

Unbelievable stuff! arxiv.org/abs/2610.067... APSP and 3SUM refuted!! This is big.

The Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs" Also: - Public posting requirement - Required video submission and more. Deadline: ⏰ Nov 2, AoE acm-stoc.org/stoc2027/sto...

Sahil Singla: The Matroid Secretary Conjecture is True https://arxiv.org/abs/2609.14555 https://arxiv.org/pdf/2609.14555 https://arxiv.org/html/2609.14555

Outstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2026/... 👀

Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group: youtu.be/uOQvzLjJK6c

This new 'journal for talks' looks pretty cool: www.mathematicaldiscourse.org

Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

FOCS 2026 Test of Time call for nominations is out: tc.computer.org/tcmf/2026/05... Please submit your nominations! More info on the award here: tc.computer.org/tcmf/focs-te... and here's DBLP links for FOCS '16, '06, '96: dblp.org/db/conf/focs... dblp.org/db/conf/focs... dblp.org/db/conf/focs...

Sidhanth Mohanty now has a blog! sidhanthm.com/bubbles/john...

Congratulations to Charles H. Bennett and Gilles Brassard on receiving the 2025 ACM A.M. Turing Award! They are recognized for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing. awards.acm.org/turing @umontreal

Very inspiring and poignant talk by the great John Watrous on (quantum) education at QIP2026. (Check out the video when it's available, or his quantum course youtube.com/playlist?lis... while you wait.)

Kewen Wu on "No exponential quantum speedup for SIS∞ anymore"... Or if you prefer a special case, "Subset-Sum with vectors mod 3": www.youtube.com/watch?v=Pl2b...

Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky

Feeling depressed and anxious about the state of the world? Try working on a 375 year-old math problem from the Platonic realm, which should be completely psychologically safe . . . youtu.be/QH4MviUE0_s

Please take a minute and nominate your favourite paper from FOCS 1995, 2005, or 2015 for the FOCS Test Of Time Award! 1995 papers: dblp.org/db/conf/focs... 2005 papers: dblp.org/db/conf/focs... 2015 papers: dblp.org/db/conf/focs... Nomination instructions here: tc.computer.org/tcmf/2025/08...

NSF announces funding for ICARM: the Institute for Computer-Aided Reasoning in Mathematics, based in Carnegie-Mellon . Amazing! Carnegie-Mellon press release here: www.cmu.edu/news/stories... www.nsf.gov/news/nsf-inv...

After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available. arxiv.org/abs/2507.11536

New work with @booleananalysis.bsky.social! We prove instance-optimal bounds for quantum state certification when testers can measure all copies simultaneously, finding that the optimal copy complexity depends on how close to maximally mixed the hypothesis state is. arxiv.org/abs/2507.06010 1/3

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan-- cs.unibocconi.eu/call-nominat... (Intent-to-nominate letters due by July 31.)

Sigbovik's looking good this year. Come for the tom7/suckerpinch video preview, stay for Shor vs a random number generator...

#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th. Apply here: stoc2025theoryfest.netlify.app

New paper: Simulating Time With Square-Root Space people.csail.mit.edu/rrw/time-vs-... It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}]. To appear in STOC. Comments are very welcome!

Group theory puzzle. We have symbols ♀️,🏁,♂️. Also define ♕=♀️🏁♀️⁻¹🏁⁻¹ and ♔=♂️🏁♂️⁻¹🏁⁻¹. We posit: ♀️♕=♕♀️ and 🏁♕=♕🏁 and ♂️♔=♔♂️ and 🏁♔=♔🏁. And we posit: ♀️²⁰²⁵=🏁²⁰²⁵=♂️²⁰²⁵=1 (identity). Can you prove ♕♔=♔♕?

Bravo to 1st-year undergraduate Tyler Yang at CMU, who was the first person to write up and make videos for all* 100 exercises in my "Quantum Computer Programming in 100 Easy Lessons" series! (www.youtube.com/watch?v=XtDJ...) *more or less all

Random d-regular graphs are (2-sided) Ramanujan with probability 69%: arxiv.org/pdf/2412.20263 by Jiaoyang Huang, Theo Mckenzie, HT Yau. In particular, infinitely many 7-regular Ramanujan graphs exist.

In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders. It's kind of about group theory, though. toc.csail.mit.edu/node/1671 Besides coauthor Noah Singer (@singerng_), here's the cast of characters:

Bhangale, Khot, Liu, and Minzer improved the bounds for combinatorial lines of length 3, established in the Polymath project on the Hales-Jewett problem. Interestingly, this is done from a TCS perspective using pseudorandomness and inverse theorems for CSPs. eccc.weizmann.ac.il/report/2024/...

Great new quantum algorithm for approximate polynomial interpolation on the arXiv today: "given a uniformly random vector y of F_q^q, some integers k<q and u < q/2, find a polynomial P(x) of degree <k such that |P(i)-y_i| < u for all i". quantum computers can help here (1/4)