Dear colleagues,
If you have a result that follows from the claimed refutation of the Exponential Time Hypothesis (ETH), or a related result you would like to share, please announce it in the comments below.
Please give your full name and affiliation, name any coauthors, and state the result in a few sentences. Include a link to a paper or note that establishes the claim. If the result uses a reduction or a particular idea from the proof, please say how.
Please also send the document link in a separate email to rpaturi@ucsd.edu so we can add it to the ETH_Repository.
-Mohan Paturi (UC San Diego)
11 replies on “New Results Related to ETH”
I am maintaining a spreadsheet collecting cryptography-related algorithmic consequences of the ETH refutation. If you know of a result that’s missing from the spreadsheet, please suggest it through this google form or by emailing me at agupte@mit.edu.
Carmen Strassle and I are working together on a note showing that OpenAI’s result implies NTIME(t) subseteq DTIME(2^{o(t)}). The basic idea for obtaining inclusion in DTIME(2^{O(t lg lg t/ sqrt{lg t}}) is summarized in this tweet (https://x.com/b_subercaseaux/status/2115101024536969686). Carmen then divised a way of getting inclusion in DTIME(2^{O(t / sqrt{lg t}}), using a generalization of Cook—Levin, and an algorithmic consequence of OpenAI’s result that is not explicitly in their preprint, but for which we have formal verification.
Carmen Strassle and I are working together on a note showing that OpenAI’s result implies NTIME(t) is contained DTIME(2^{o(t)}). The basic idea for obtaining inclusion in DTIME(2^{O(t lg lg t/ sqrt{lg t}}) is summarized in this tweet (https://x.com/b_subercaseaux/status/2115101024536969686). Carmen then devised a way of getting inclusion in DTIME(2^{O(t / sqrt{lg t}}), using a generalization of Cook—Levin, and an algorithmic consequence of OpenAI’s result that is not explicitly in their preprint, but for which we have formal verification.
Stacy Gildenston and Pyrate Ruby Passell, 3primitives.io, Melbourne, Australia.
A related result, using no reduction or idea from the ETH proof: no AI-generated result carries its own authority. AI Cannot Govern AI (FR02, published 10 January 2026) proves that no total computable function resolves authorisation without an exogenous declaration.
Canonical Logic Sequence (FR01) separates authority from outcome: a correct result does not settle who answers for it.
For the ETH claim, a proof checker can confirm the derivation against its own statement. It cannot declare that the statement is ETH as the field means it, or answer for the results rebuilt on it.
Named people must make that declaration, at release. Where no one does, what operates is authority owned by no one (Ghost Authority Lemma, FR05). This holds whether ETH stands or falls.
The records, public and DOI-registered: https://3primitives.io/formal_records/
I have applied my Ram Calculus approach to improve/extend the ETH paper by OpenAI. See http://www.integralresearch.net for some information on Ram Calculus. Below is a summary of a long technical report I have. I will post the full report on github in a few days.
Summary:
This report summarizes the conceptual, mathematical, and computational contributions
of the research monograph Ram Calculus and Exact Counting. The central contribution is
a certified exact-representation framework applied to specific routines in OpenAI’s archived
exponential-time-hypothesis manuscript: the counting observable, coefficient algebra, future
updates, and recovery precision are specified together. This leads to an aggregated Boolean-jet
identity, conditional weighted-support reductions, target-specific precision certificates, symmetry
and closure tests, exact four-state packet representations, closed higher-mode sums, and shared
coefficient construction. The report explains the hypotheses and significance of these results,
the distinction between new application-level contributions and classical mathematics, and the
recorded experimental gains and failures. Several finite comparisons show substantial runtime
reductions, but memory benefits are not uniform. The strongest optimized six-coefficient baseline
matches the direct four-state builder’s multiplication and addition counts and yields mixed
pipeline timings. No improved unrestricted SAT exponent, general hard-instance superiority, or
independent proof of the source manuscript’s full headline claim is established.
Assuming the counting theorem of OpenAI (Thm 1.1) / Anthropic (Thm 1), I give deterministic algorithms with explicit rates for problems whose 2^o(k) lower bounds (Cai–Juedes 2003) rested on ETH. Vertex Cover runs in 2^O(k log log k/√log k) + poly(n). Max-Cut and Max-c-SAT run in 2^O(k/√log k) + poly(n). On bounded-degree graphs, Independent Set, Vertex Cover and Dominating Set run in the same 2^O(k/√log k) + poly(n) time, and dominating sets can also be counted. Qualitatively these follow from Cai–Juedes and Anthropic’s Cor. 7; the contribution is the explicit rates with short proofs. Each proof uses a linear kernel and then a count-preserving CNF encoding with O(k) variables, including a linear-size cardinality gadget, and calls the counting algorithm as a black box.
https://formalize.now/378 compares OpenAI’s Math 378, Anthropic’s ETH formalization, and standard ETH using Reading Point Identifiers (RPIs) for theorem statements and implications. The goals are: distinguish kernel-checked results from remaining formalization gaps; and provide a reproducible verification roadmap. Find repo from that link; feedback welcome.
I am working on the simplification and understanding of the recent proofs of ETH refutation. I come up with two new proofs about ETH refutation which are relatively short, easy to follow, and that show why the argument works. Both proofs are formalized in Lean 4 down to a primitive multitape machine. They are currently available at https://github.com/suquark/NotETHSimplified. I will keep updating the repo if I have new interesting results.
1. Using Anthropic paper, every fan-in-2 circuit of size s, of any depth, is equivalent to AC^0[q] circuit (q odd) of (about) small depth and subexponential size (constant depth gives 2^eps n size, and depth O(log log s) gives size 2^{O(s/log^{0.125} s)}. This extends Valiant’s depth reduction, so as a consequence, exponential lower bounds against such circuits would already give strong lower bounds for general circuits
link
2. NTIME_RA[t] ⊆ DTIME[2^{O(t/√log t)}]. This one came directly out of Ryan William’s tweet
link
I have two notes on Zenodo following the recent claimed refutations of the ETH.
In neither note do I use a reduction or an idea from the preprints’ proofs. In the second I take the parameters as set in OpenAI’s preprint
Stefan Szeider
TU Wien
https://ac.tuwien.ac.at/szeider
My paper improves Anthropic’s 3-SAT algorithm to drop its crossover point* from 2^33858 to 2^417 clauses for #3-SAT at density 1.
*where its main term beats the best known algorithms, a stricter bar than Szeider’s comparison with exhaustive search
It also proves that no algorithm of this kind can gain for general 3-SAT below ~2^6000 variables (in the main-term model), unless it leaves the grid structure of Anthropic’s algorithm.
For OpenAI’s algorithm, the crossover point of its Appendix D route is ~2^(4.4·10^10) (estimate).
https://arxiv.org/abs/2610.41622