I'm releasing a series of videos called "Quantum Computer Programming in 100 Easy Lessons".

youtube.com/playlist?list=…

It will cover the 'usual' content (...CHSH, Grover, Factoring), but with some expositional innovations that I *hope* will make it easier for beginners.

I finished the proof of "ETH false" (#3SAT in subexponential time) in my grad complexity class at CMU today (mod some easy exercises).

I think it's nice that it can be done just using classical complexity theory ingredients - it fits well in the course!

youtube.com/watch?v=3CdlC4…

I lectured on the "ETH false" (#3SAT in subexponential time) result in my grad complexity class at CMU today.

Didn't have time in 80 mins to do the full proof, but I hope I got across the main plan, and some of the basic TCS ingredients going into it.

youtu.be/_HlQGMcQWhA

#ETH: I hit the annoying max-chat-length, so good time to pause.

cs.cmu.edu/~odonnell/some…
Still badly written, but I'm happy with this progression of ideas for # 3SAT (sparse permament) in time ~2^(n/sqrt(log n)).

It's 5-page overview, 10 pages of stuff, 5 page bonus appendix.

Assuming correctness, it seems extremely likely, if not already a direct consequence, that NTIME[t] subseteq DTIME[2^{o(t)}]. It comes down to reducing the auxiliary variables in the CNF encoding of NTIME-acceptance!

Making some progress on simplifying the '#ETH false' proof, I think. In latest version, the key algebraic construction comes from elementary analysis of Boolean functions.

cs.cmu.edu/~odonnell/some…

A couple of my course lectures about ETH and SETH and related things:

youtube.com/watch?v=dVQrj5…

youtube.com/watch?v=NMOMDz…
(From last week!)

I will be the first to admit, I was repeatedly on the record as believing SETH :-)

Here's a direct link to OpenAI's PDF claiming a refutation of ETH. In particular, it's claimed that 3SAT on n variables is in about exp(n/(log n)^{1/2+o(1)}) time
github.com/openai/math/bl…

William Hoza on the BPL=L result:

youtube.com/watch?v=2hVv47…

Happy to share that our better-than-2 approximation results for k-median are now on arXiv:

arxiv.org/abs/2610.18144
arxiv.org/abs/2610.17172

It has been a pleasure working with this fantastic group: @rares_buhai , Vincent Cohen-Addad, Henry Fleischmann, @anupamg , Antoni "Toni" Jubés Monforte, Madhusudhan Reddy Pittu, @mstou73, and @LukasBirdyy

A special shout-out to Toni, who started working on this problem for his Master's thesis almost two years ago. His work led to the impressive analysis of the factor-revealing LP!

Now on to other things...

I looked forward to this cleanup! Nikloai Chukhin (eccc.weizmann.ac.il/report/2026/24…) significantly cleans and extends the OpenAI 2^(ω(sqrt(n))) lower bound for depth-3 circuits:

The (4n-1)-bit function sum_ij a_{i+j}x_iy_j mod 2 needs depth-d circuits of size 2^(Ω~(n log n)^{1/(d-1)}).

Sorry for spelling @buyolitsez2's name wrong; obviously it is 'Nikolai'.

this is great: a unified and transparent exposition of the recent breakthroughs on the decoding of Reed-Solomon codes.
eccc.weizmann.ac.il/report/2026/23…

The what now?!
arxiv.org/abs/2610.06783…

oh that's interesting! The authors share the draft generated by Astra, as a companion to their arxiv submission.
arxiv.org/abs/2609.28028

STOC 2027 Call for Papers is out:
acm-stoc.org/stoc2027/stoc2…

Note quite a lot of changes from previous STOC CfPs.

An amazing result in online algorithms. I worked on this for over a decade and it is fantastic to see a solution that looks very clean! Also great to see an expert behind the wheels. Congratulations @sahilsingla81 arxiv.org/abs/2609.14555

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

h/t to Noah Singer @singerng_ for pointing me to the paper

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 youtube.com/@ComplexityThe… 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