Subexponential Hamiltonian cycle counting derived from OpenAI/Anthropic ETH refutations, verified in Lean
xennygrimmato_ · x · 2026-10-28
Building on the claimed ETH refutations posted by OpenAI (openai/math) and Anthropic (anthropics/formal-math) on Oct 26, a researcher derived a new result and open-sourced the full paper and Lean proofs (repo: eth-hamiltonicity):
- Main result: assuming the refutations hold, the exact number of Hamiltonian cycles in sparse graphs (|E| = O(n)) can be computed deterministically in subexponential time — previously the best algorithms for general sparse graphs were exponential.
- Sharper rate: the paper gives 2^{O(n/√log n)}, matching the new SAT algorithms.
- Formal verification: the subexponential bound is machine-checked in Lean, built on top of rebuilt versions of both labs' proofs.
- Caveat: results are asymptotic, conditional, and the ETH refutations are still pending human expert review.
Related event: Subexponential Hamiltonian Cycle Algorithm Built on ETH Refutation(3 posts)→
More from Research
- OpenSIR: a self-play framework lets LLMs teach themselves math with zero training data — PMinervini · 2026-10-28
- Mechanistic interp as a meme: poking the neurons that make Qwen 'go homicidal' — sebkrier · 2026-10-28
- Open-source agent memory layer Mind hits 86.67% on LongMemEval without embeddings — GabrielMartinMoran · 2026-10-28
- Proposal: a public challenge to find the shortest prompt reproducing each arXiv paper's results — tak3sh8 · 2026-10-28
- Piano2Pop expands piano demos into full pop productions without aligned supervision — affige_yang · 2026-10-28
- RAX lets a real robot explore for 2 hours and turn learned skills into reusable code — no demos needed — du_yilun · 2026-10-28