Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?

OpenAI released solutions to three blockbuster math problems that have long vexed researchers yesterday. One was a surprise rejection of the Exponential Time Hypothesis (ETH), a durable assumption in computer science that plays a large role in how we understand what is difficult to compute.

As with previous proof-drops from the frontier lab, scientific communities responded with a mixture of thrill and dismay. Anthropic mathematician Levent Alpöge suggested that OpenAI was basing its solutions from pre-existing work, and hours later, Anthropic subsequently released its own refutation of ETH.

However, OpenAI’s process is evolving. This time, the lab structured its releases differently for each of the three disciplines involved: Mathematicians got the work dropped on GitHub; the computer scientists formed a working group, asked for the proofs to be shared publicly and OpenAI to fund a conference to discuss them; the physicists formed a working group that will determine how their result will be released.

MIT Professor Ryan Williams is the computer scientist who is organizing his field’s response to the new finding. Williams, whose work focuses on these questions of computational complexity, has criticized OpenAI’s approach in the past, calling its proof dump earlier this October a “DDOS attack on mathematicians.”

However, he agreed to collaborate with the frontier labs in order to help shepherd ideas that are vital to the field, he told TechCrunch. The lab asked him to help interpret the solution, along with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999.

Their first step was to release an open letter calling for feedback from scientists interested in these problems and a discussion of the norms around AI contributions to their work.