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

Clément Canonne

@ccanonne.github.io

Read the document, which goes beyond this (huge) claim and calls for important discussions.

26/10/26, 9:47 pm0 reposts4 likes

Clément Canonne

@ccanonne.github.io

18h

Ryan's thread: bsky.app/profile/rrwi...

Ryan Williams@rrwilliams.bsky.social

An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4

Clément Canonne

@ccanonne.github.io

Also, *Hypothesis in the first post. Nobody has said anything about the Exponential Time Hypothetis, as far as I know.

Morten Grøftehauge

@drgroftehauge.bsky.social

Have you heard the good word of John Mastodon? John Mastodon would have let you edit that post.

David Picard

@davidpicard.eurosky.social

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.

Marc Lanctot

@sharky6000.bsky.social

17h

Wow, quite a departure from the Navier-Stokes story. Nice to see! Crazy times ahead.. curious what will come of this.

Marc Lanctot

@sharky6000.bsky.social

17h

Btw I am quite far out from TCS.. would this have any implications for P vs. NP or any other complexity class relationships?

Clément Canonne

@ccanonne.github.io

17h

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