Post

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...

7 reposts38 likes

Step 2a) if they supply lean code, invite lean experts to examine it. The definitional surface area will almost certainly be large. Give them access to good models to help understand and simplify the lean proof. Step 2b) simultaneously let TCS experts discuss ETH as well as the other questions.

The google docs letter was written by AI. The older placeholder fields made it clear (i only have a copy of them, but pangram also checks the rest as AI generated).

I'm really curious: what's your opinion on this communication / dissemination approach by openAI as opposed to their previous approaches? Can you anticipate any serious problems with this approach? Thanks!

If Thetis exists (or existed- depending on your views on gods and goddesses) it seems logical that an Hyperthetis and an Hypothetis exist as well. What's that to do with exponential time, I don't know.

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.)