OpenAI's ETH refutation met with skepticism as Anthropic releases its own

OpenAI's release of solutions to three blockbuster math problems, including a refutation of the Exponential Time Hypothesis, marks another proof-drop from a frontier lab that has previously drawn mixed reactions from scientists. This time, the response from the computer science community is being organized by MIT Professor Ryan Williams, who has criticized OpenAI's approach in the past, calling an earlier proof dump a "DDOS attack on mathematicians." Williams agreed to collaborate with the labs, along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999. Their first step was an open letter calling for feedback and a discussion of norms around AI contributions.

Williams told TechCrunch that parts of OpenAI's proof are "maybe you could say routine," but there are "two or three alien-looking parts" that convinced him the whole community needs to work on it together. He also said the result calls into question intuitions about how tractable hard NP problems are, but added, "I also think that this is probably not the final answer either. I don't think that OpenAI's algorithm could possibly be the best algorithm you can get." The durability of the ETH means many scientific papers over the past decade will need to be revisited if the claims hold up, which is partly why Williams pushed OpenAI to support a conference.

Before scientific concerns, there are cybersecurity questions. Williams said an improved algorithm could imply that cryptographic systems relying on certain key sizes could be considered broken, so he asked OpenAI science lead Dan Roberts whether they had checked for crypto impacts. According to Williams, they checked and were reasonably confident the result did not imply any breaks. Williams says he is optimistic despite real concerns, particularly about training the next generation of scientists, and that AI is forcing people to be more ambitious about the kind of work they do.