Videos: https://xitter.twitterapi.xyz/t.co/vy9r4V6aOZ
Pittsburgh, PA
Joined October 2011
- Tweets759
- Following0
- Followers8.1K
- Likes1.6K
I made this with AI, but it basically follows the plan of the lectures: cs.cmu.edu/~odonnell/some_et…
12
1,465
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…
The pieces you stitch together are permanents of structured nxn matrices, structured enough that you can compute their permanents in slightly subexponential time. Anyway, maybe this is just a question of semantics :)
244
I'm not totally sure. Maybe. To me, the oai proof (and also the ant one) are 'algebra'. Roughly, compute per(A) by making A(t) such that A=A(0), and per(A(1)), ..., per(A(ℓ)) are easy to compute by being structured. (Ant proof just has a more awkward way of doing this, ℓ=2.)
2
497
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
Hard to say. There's arguably just one main 'trick' in the result, and that trick is stuck at sqrt(log n). But once you start to look for new tricks of similar types, I have no idea what could happen.
6
747
#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.
Ryan O'Donnell retweeted
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!
Not to pick sides, but it's basically 100% the OpenAI one. I asked my LLM if the Anthropic one had ideas to incorporate, but I don't think we used any.
9
2,054
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)}).