Computer Scientists Facilitating Independent Review of a High-profile OpenAI and Anthropic Result
Researchers from UC San Diego and MIT are launching an independent review of claims by OpenAI and Anthropic that their models refuted the Exponential Time Hypothesis.
Deep dive
- The Core Claim: OpenAI and Anthropic claim their models successfully refuted the ETH, a foundational hypothesis in computational complexity.
- Independent Scrutiny: The academic community is organizing a formal review process, including a dedicated blog and upcoming academic conferences to vet the results.
- Historical Context: The ETH was formulated in 1998 by Impagliazzo and Paturi. The current verification effort seeks to ensure that results generated by LLMs hold up to rigorous mathematical standard.
- Implications: Successful refutation of the ETH would likely require a total reassessment of security assumptions in modern encryption protocols.
Decoder
- Exponential Time Hypothesis (ETH): A fundamental assumption in computational complexity that suggests certain problems (like 3-SAT) cannot be solved in sub-exponential time; it is the basis for many lower-bound results in computer science.
- Sub-exponential time: Algorithms that run faster than exponential time, which is considered the practical limit for solving NP-complete problems.
Original article
Computer Scientists Facilitating Independent Review of a High-profile Open AI and Anthropic Result
Both companies announced their models refuted the Exponential Time Hypothesis formulated by UC San Diego computer scientists
In case you missed the global media coverage including The New York Times, UC San Diego computer scientists Russell Impagliazzo and Mohan Paturi as well as MIT computer scientist Ryan Williams are facilitating an independent review of a high-profile result generated by two frontier AI labs, Open AI and Anthropic.
Both companies recently announced that their AI models have refuted the highly influential Exponential Time Hypothesis (ETH). If the findings hold, the refutation of ETH (and/or the rise of possible alternatives to ETH) could have broad implications for optimization algorithms and a wide range of applications in chip design, encryption systems used on the Internet, and much more.
Now that the future of ETH is a topic of hot discussion, Impagliazzo, Paturi and Williams have stepped into the role of helping the computer science community understand and assess the ETH claim independently.
Impagliazzo and Paturi are both professors in the UC San Diego Department of Computer Science and Engineering. Paturi is also the associate dean for artificial intelligence strategy and implementation at the UC San Diego Jacobs School of Engineering.
The team launched ETH: Community Examination and Discussion, a new blog that serves as a place for researchers to share findings and ideas regarding the future of ETH.
The team plans to hold one or more academic conferences, where verification work will be discussed, along with farther-reaching implications. This week on the blog, the team posted the OpenAI prompt that led to the ETH refutation.
ETH was proposed in 1998 by Impagliazzo and Paturi, with then-computer science PhD student Francis Zane, who is now an independent researcher.
Fresh dev news, AI-digested daily. Never miss a trend at devoured.fyi