Researchers coordinate independent review of OpenAI and Anthropic’s ETH claim
OpenAI and Anthropic announced that their models had refuted the Exponential Time Hypothesis, proposed in 1998. Two of its authors, Russell Impagliazzo and Mohan Paturi, are now coordinating an independent review of the claim with MIT’s Ryan Williams.
For now, the refutation is the companies’ own claim. UC San Diego’s news service wrote on 19 November that the result could have broad implications if it holds up under scrutiny. The higher-education newsletter Fogbell summarised the story and noted that the claim had not yet been verified. The news has been widely reported, including by The New York Times, but coverage is no substitute for checking the result.
The Exponential Time Hypothesis (ETH) is an assumption in computational complexity theory. It holds that the satisfiability problem for logical formulas (3-SAT) cannot be solved substantially faster than in exponential time. In the worst case, solving time therefore grows exponentially with the number of variables. Impagliazzo and Paturi proposed the hypothesis in 1998 with Francis Zane, then a graduate student in computer science.
UC San Diego said that the refutation of ETH, or alternatives proposed to it, could affect optimisation algorithms and many applications, such as circuit design and encryption systems used on the internet. The implications are therefore conditional: they depend on whether the result holds.
Impagliazzo and Paturi are professors of computer science at UC San Diego. Together with Williams, they launched the blog ETH: Community Examination and Discussion, where researchers can share findings and ideas about the future of the hypothesis. In the week UC San Diego published its story, the team posted the OpenAI prompt that produced the refutation on the blog. This lets other researchers examine how the result was produced.
The team also plans one or more academic conferences to discuss the verification work and wider implications. Readers can follow the fate of the claim on the blog, where the research community’s assessment is accumulating.