ETH refutation spawns crypto speedups: ECDL and lattice problems get subexponential gains
rrwilliams · x · 2026-11-02
Tracking the fallout of the claimed ETH refutation, MIT's Aparna Gupte maintains a public spreadsheet of cryptographic algorithmic consequences. Recorded so far: elliptic curve discrete log improved from 2^{O(b)} to 2^{O(b/(log b)^{1/4})} (announced 10/28), and Ring-LWE/Module-LWE plus an asymptotic AES variant improved from 2^n to 2^{n/sqrt(log n)} (10/29), each with papers and authors. The sheet also solicits more results and self-reported human understanding and AI/human authorship ratios. If the results hold, implications for post-quantum scheme analysis are profound.
Related event: Community Builds Tracker for Results Falling Out of Claimed ETH Refutation(2 posts)→
More from Research
- Thurston's 1994 warning revived: theorem-credit culture may hurt math as AI automates proofs — alexbilz · 2026-11-02
- AI text detection study: input:output length ratio raises miss rate by at most 5% — amplifiedamp · 2026-11-02
- Blogger Speculates on a Continual Learning Architecture Combining Multi-Stream LLMs and ECHO — joey072shx · 2026-11-02
- L3G-World Generates Minute-Long Consistent Worlds From a Single Image — Crazy-Repeat-2006 · 2026-11-02
- Fortnow revisits 3SUM, APSP and ETH: why complexity conjectures are believed — fortnow · 2026-11-02
- Why LLM steerability beats specialized models in generative bio design pipelines — chaitjo · 2026-11-02