Videos: https://xitter.twitterapi.xyz/t.co/vy9r4V6aOZ
Pittsburgh, PA
Joined October 2011
- Tweets759
- Following0
- Followers8.1K
- Likes1.6K
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.
No.
@AAmbainis and John Watrous gave an unconditional proof of quantum supremacy (a quantum Turing machine solving a problem exponentially faster than any classical TM using the same (small) memory budget, including as yet undiscovered ones) about 25 years ago.
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…
Do you have the lecture notes or exposition of the proof written somewhere? Couldn't find it on your website :(
1
2
1,701
I made this with AI, but it basically follows the plan of the lectures: cs.cmu.edu/~odonnell/some_et…
12
1,463
I’m curious for those who spent much more time thinking about this … was there any reason to believe ETH should be true? (other than some smart people had thought about it but didn’t find a faster algorithm yet?)
“Nothing better than brute force exists” was already false, with a series of papers getting c^n for c<2 smaller and smaller, which (hindsight is 20/20 of course) could make one feel a bit bearish about ETH.
For the reader who doesn’t realize, getting *some* c<2 is basically trivial. Look at the first clause and recursively try all 7 settings of its variables which don’t falsify it and skip the 8th.
T(n) = 7*T(n-3) leads to 7^{n/3} = O(1.913^n).
Indeed the "stitching together in P" is being done by algebra. But ultimately it's a structured exp size instance, unless your proof is radically different from OpenAI's
1
406
I believe the OpenAI one belongs to a class of algorithms that reduces an NP problem to an exp large instance of a P problem, by breaking vars into pieces, enumerating all assignments within pieces, and using a P problem to "stitch" them together. I called these "split and list"
2
583
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.
Do you have a sense where the limit of this method is? E.g. do you expect that the 1/2 exponent on the log can be improved with refinements of this method?
1
5
1,237
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!
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…
This is great, thank you!
Is it based solely on the OpenAI proof, or did you also draw inspiration from the Anthropic proof?
2
6
2,511
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 :-)
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/…
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
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)}).