I'm releasing a series of videos called "Quantum Computer Programming in 100 Easy Lessons".
youtube.com/playlist?list=PL…
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=3CdlC4XO…
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_et…
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_et…
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/blob/…
Happy to share that our better-than-2 approximation results for k-median are now on arXiv:
arxiv.org/abs/2610.18144arxiv.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...
OpenAI completely solved a problem on which my students have worked hard for 1+ years and made significant progress. They should be proud to have pushed on a problem appearing in this historic list of ~400 results.
We’ll soon upload our different algorithmic approach to k-median.
I looked forward to this cleanup! Nikloai Chukhin (eccc.weizmann.ac.il/report/2…) 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)}).