iiinova — where your digital self keeps evolving

Reposted by Ryan O'Donnell

Clément Canonne @ccanonne.github.io · 17/09/2026

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...

Policy experiments for STOC 2027: In light of rapid advances in generative AI and their impact on research and scientific communication, STOC 2027 is experimenting with several new policies intended to encourage high-quality submissions and promote clear and effective communication of research. The policies below include mandatory public posting and mandatory video submission. Detailed instructions for these two requirements will be released closer to the paper submission deadline.

44014

Ryan O'Donnell @booleananalysis.bsky.social · 15/09/2026

... one might strive further to get the best of both worlds: "Rich" 2-to-1 with perfect completeness (eccc.weizmann.ac.il/report/2019/...). That would imply both results. Perhaps the rumors might concern this?

eccc.weizmann.ac.il

ECCC - TR19-141

110

Ryan O'Donnell @booleananalysis.bsky.social · 15/09/2026

I guess this result is morally close to 2-to-1 Conjecture with perfect completeness. (Maybe with tweaking you can get 4->2, who knows.) Then it's true that UGC is somewhat different, being stronger in one sense (1-to-1) and weaker in another (imperfect completeness). But...

121

Ryan O'Donnell @booleananalysis.bsky.social · 14/09/2026

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

eccc.weizmann.ac.il

ECCC - TR26-179

3237

Ryan O'Donnell @booleananalysis.bsky.social · 10/09/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.

youtube.com

Complexity Theory At Carnegie Mellon

05717

Ryan O'Donnell @booleananalysis.bsky.social · 04/09/2026

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

youtu.be

A non-sofic group

YouTube video by Ryan O'Donnell

0130

Reposted by Ryan O'Donnell

Nutan Limaye @nutanlimaye.bsky.social · 04/06/2026

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

2498

Ryan O'Donnell @booleananalysis.bsky.social · 18/05/2026

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...

064

Reposted by Ryan O'Donnell

Association for Computing Machinery @acm.org · 18/03/2026

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

14817

Ryan O'Donnell @booleananalysis.bsky.social · 28/01/2026

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.)

0251

Ryan O'Donnell @booleananalysis.bsky.social · 18/01/2026

I think it's fine but only if you also subscribe to my preferred (and minority) take on the meaning of "O(n^2)", namely that it stands for an anonymous function f(n), with the property that f(n)/n^2 is bounded, that you don't care to make explicit...

000

Ryan O'Donnell @booleananalysis.bsky.social · 18/01/2026

The one I really really wish people would accept is "If m >= O(n^2) then..." to mean "There exists a constant C such that if if m >= Cn^2 then...".

110

Ryan O'Donnell @booleananalysis.bsky.social · 31/12/2025

Etymology of Idaho is even funnier!

130

Ryan O'Donnell @booleananalysis.bsky.social · 26/11/2025

I think it's just a name made up by Nati Linial. First appearance seems to be from "The Influence Of Large Coalitions", but the function dates back to Ben-Or and Linial's collective coin-flipping paper.

130

Ryan O'Donnell @booleananalysis.bsky.social · 25/11/2025

Hat tip to Aniket Das on twitter, where I saw this... x.com/ketd47

020

Ryan O'Donnell @booleananalysis.bsky.social · 25/11/2025

Wow! Yuansi Chen resolves 1 of the 2 remaining $1000 Talagrand problems (michel.talagrand.net/prizes/prize... ): If you take any f : {-1,+1}ⁿ → ℝ⁺ and apply the noise operator T_{.99}, the resulting function g = T_{.99} f satisfies a better-than-Markov inequality. That is, Pr[g > t E[g]] < o(1/t).

michel.talagrand.net

2444

Ryan O'Donnell @booleananalysis.bsky.social · 05/11/2025

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...

youtube.com

No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu

YouTube video by Institute for Advanced Study

0101

Reposted by Ryan O'Donnell

Clément Canonne @ccanonne.github.io · 30/10/2025

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

2373

Ryan O'Donnell @booleananalysis.bsky.social · 28/10/2025

I do not, I'm afraid. I guess it's space efficiency vs time efficiency vs pedagogy; perhaps an expert can chip in...

020

Ryan O'Donnell @booleananalysis.bsky.social · 11/10/2025

This paper looks incredible, by the way.

030

Reposted by Ryan O'Donnell

Dr. Tom 7 Murphy VII Ph.D. ! @tomvii.bsky.social · 16/09/2025

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

youtu.be

Rupert's Snub Cube and other Math Holes

YouTube video by suckerpinch

38517

Ryan O'Donnell @booleananalysis.bsky.social · 26/08/2025

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...

tc.computer.org

FOCS Test of Time Award - Call for Nominations 2025 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing

FOCS 2025 Test of Time Awards Call for Nominations The 2025 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of...

020

Reposted by Ryan O'Donnell

xenaproject.bsky.social @xenaproject.bsky.social · 04/08/2025

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...

nsf.gov

NSF invests over $74 million in 6 mathematical sciences research institutes

The U.S. National Science Foundation is investing over $74 million in six research institutes focused on the mathematical sciences and their broad applications in all fields of science, technology and...

1167

Reposted by Ryan O'Donnell

John Watrous @johnwatrous.bsky.social · 16/07/2025

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

arxiv.org

Understanding Quantum Information and Computation

This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...

515334

Reposted by Ryan O'Donnell

Chirag Wadhwa @emose.bsky.social · 09/07/2025

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

Screenshot of the title and abstract of https://arxiv.org/abs/2507.06010.

1151

Ryan O'Donnell @booleananalysis.bsky.social · 09/06/2025

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.)

cs.unibocconi.eu

14718

Ryan O'Donnell @booleananalysis.bsky.social · 20/05/2025

J-Live's Braggin' Writes has my top 'thesis' verse, though. ("I displays my credentials over instrumentals...")

010

Ryan O'Donnell @booleananalysis.bsky.social · 17/05/2025

This! I like to say, "Let p|A denote distribution p conditioned on event A. Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A. Except you don't have to imagine, because it's literally our world! Now explore probabilistic algorithms in this world."

1324

Ryan O'Donnell @booleananalysis.bsky.social · 04/04/2025

There's a reason I called it Quantum Computer Programming in 100 Easy Lessons.

060

Ryan O'Donnell @booleananalysis.bsky.social · 04/04/2025

Meming aside, this looks like a cool paper...

130

Ryan O'Donnell @booleananalysis.bsky.social · 02/04/2025

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

040

Reposted by Ryan O'Donnell

Anupam Gupta @anupamg.bsky.social · 27/02/2025

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

stoc2025theoryfest.netlify.app

Vite + React + TS

097

Reposted by Ryan O'Donnell

Ryan Williams @rrwilliams.bsky.social · 21/02/2025

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!

people.csail.mit.edu

1726475

Ryan O'Donnell @booleananalysis.bsky.social · 10/02/2025

[...] "x1 += x2" and "x1 += x3". Similarly for "x2 -= x4". Finally, we posit: Doing "x1 += x2" 256 times in a row is equivalent to doing nothing (maybe shoulda called it "x1 += x2 mod 256") and sim. for doing "x2 += x3", "x3 += x4" 256x in a row. Can you prove "x1 -= x3" commutes with "x2 -= x4"?

010

Ryan O'Donnell @booleananalysis.bsky.social · 10/02/2025

PL puzzle. Say we have instructions called "x1 += x2", "x2 += x3", "x3 += x4", and versions with "-=" that cancel them. We define a program "x1 += x2" "x2 += x3" "x1 -= x2" "x2 -= x3", and abbreviate it "x1 -= x3". We similarly define "x2 -= x4". We posit that "x1 -= x3" commutes with [...]

110

Ryan O'Donnell @booleananalysis.bsky.social · 08/02/2025

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

030

Ryan O'Donnell @booleananalysis.bsky.social · 09/01/2025

... which is to formalize the analogous theorems for the B_3 case (specifically, Sec. 8 of my recent paper with Noah: arxiv.org/pdf/2411.05916). The proofs there are 70 pages of Noah solving the word problem by hand. So it will be nice to have a computer check his work -- a team is being assembled!

arxiv.org

070

Ryan O'Donnell @booleananalysis.bsky.social · 09/01/2025

Cayden Codel & Noah Singer have formalized in Lean the climactic theorems of the Kaufman-Oppenheim paper that shows the A_3-type coset complex HDXs are cosystolic expanders! (I.e., Sec. 7.2 of arxiv.org/abs/1907.01259) It's a warmup for the main project...

arxiv.org

191

Ryan O'Donnell @booleananalysis.bsky.social · 08/01/2025

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

youtube.com

#1/100: Toggling qubits || Quantum Computer Programming in 100 Easy Lessons

YouTube video by Ryan O'Donnell

0131