Conditional subexponential algorithm for counting Hamiltonian cycles in sparse graphs, leaning on claimed ETH refutations
xennygrimmato_ · x · 2026-11-01
A paper on Hexagon (marked primarily AI-generated, by Vaibhav Tulsyan) derives a conditional corollary of the claimed October 2026 ETH refutations: assuming three internal results of the Anthropic manuscript hold, the number of Hamiltonian cycles in an n-vertex graph with O(n) edges can be computed exactly and deterministically in 2^{O(n/√log n)} time, with the bound formally verified in Lean. Corollaries cover exact sparse TSP, directed cycle counting, and ATSP. The author stresses it is not a standalone breakthrough — it stands or falls with the claimed refutation.
More from Research
- Can LLMs turn surprising observations into research questions and discover physical laws? — rohanpaul_ai · 2026-11-01
- LongChang benchmark: GPT-6-Astra hits 16.7% discovery rate, other 11 LLMs score zero — rohanpaul_ai · 2026-11-01
- 747 AI-agent ideas reveal a scaling law for idea descent: +17% per doubling — DimitrisPapail · 2026-11-01
- Xiaomi's A-RSI lifts 11-benchmark average from 57.77 to 61.05 via adaptive task refresh — mark_k · 2026-11-01
- Berkeley/Stanford paper: agents gain up to 39% by wiping memory and restarting from best result — alexcovo_eth · 2026-11-01
- UniT framework trains unified multimodal models to plan, inspect, and refine iteratively — burkov · 2026-11-01