Videos: https://xitter.cf/t.co/vy9r4V6aOZ
Pittsburgh, PA
Joined October 2011
- Tweets749
- Following0
- Followers7.8K
- Likes1.6K
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…
A couple of my course lectures about ETH and SETH and related things:
youtube.com/watch?v=dVQrj52J…
youtube.com/watch?v=NMOMDz3x…
(From last week!)
I will be the first to admit, I was repeatedly on the record as believing SETH :-)
I discussed the paper with an LLM for a while. At the end, I had it write up a new version of the result. It's 12 pages and seems to do a clearer job of explaining the main ideas. Uses a little quantum language, sorry :)
cs.cmu.edu/~odonnell/some_et…
DISCLAIMER: no idea if it's correct
No results assuming ETH fall, per se. All these results are of the form "there is a very efficient algorithm reducing 3SAT to problem X". And these algorithms continue to work correctly.
(I kind of expect that one can use some such result to simplify the OpenAI proof a bit.)
Ryan O'Donnell retweeted
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/…
William Hoza on the BPL=L result:
youtube.com/watch?v=2hVv47LO…
Ryan O'Donnell retweeted
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/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)}).
Yeah, I just have no intuition about whether the algorithm can be made oblivious. But if you think it seems likely... that would be cool. Hopefully someone will work it out. Because this result seems noticeably more compelling to me if it also works for circuits.
Seems to me that Boolean circuits might be the most natural model for investigating the problem? Has anyone discovered anything for circuits, post-OpenAI paper?
It depends on the model, of course. In the standard model of algorithms you use in an algorithms class (namely, the RAM model with log n size registers, with multiplying two registers in time O(1) allowed), the complexity is O(n). This is not trivial, but known since the 1970s.
My GPT claims the techniques can give exponent 2/3 for RAM model. I'll try to check if this is accurate.
Ryan O'Donnell retweeted
this is great: a unified and transparent exposition of the recent breakthroughs on the decoding of Reed-Solomon codes.
eccc.weizmann.ac.il/report/2…
Ryan O'Donnell retweeted
The what now?!
arxiv.org/abs/2610.06783v1
Ryan O'Donnell retweeted
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/stoc20…
Note quite a lot of changes from previous STOC CfPs.