Post

Clément Canonne
@ccanonne.github.io

OpenAI has claimed a refutation of the Exponential Time Hypothetis (ETH). Russell Impagliazzo, Mohan Paturi and Ryan Williams (@rrwilliams.bsky.social) have been asked to organize a community-led effort to evaluate this claim. More here: docs.google.com/document/d/1... h/t @gautamkamath.com

docs.google.comMessage to the TCS Community on ETHDear colleagues, OpenAI has informed us that it has obtained a claimed refutation of the Exponential Time Hypothesis and plans to release the supporting documents to the community. Our names may appea...
Clément Canonne
@ccanonne.github.io

Not directly, afaik. Subexponential algorithms for NP problems, and revisiting a lot of what we have based on the ETH of course (including some stuff affecting standard cryptographic assumptions), but nothing as simple as collapse of standard complexity classes. (At least based on my recollection.)

0 reposts2 likes

No replies yet.