Ryan O'Donnell

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

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

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

Etymology of Idaho is even funnier!

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.

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

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

YouTube video by Institute for Advanced Study No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu

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

Hear hear!

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

YouTube video by Ryan O'Donnell #60/100: 1-qubit Rotation Estimation: Overview || Quantum Computer Programming in 100 Easy Lessons

I do phase estimation without QFT in my undergrad course. youtu.be/CMqPutlG59c?...

It's just Hadamard test plus binary search.

This paper looks incredible, by the way.

arxiv.org/pdf/2510.07788

YouTube video by suckerpinch Rupert's Snub Cube and other Math Holes

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

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

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

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

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

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

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

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

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

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

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

I did not know this!

Also Aayush Jain!

#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!

[...] "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"?