Is shaving small constants off exponents a breakthrough? Algorithm theorists debate n^1.999 results
srchvrs · x · 2026-10-07
- Context: Recent results like 3-sum in n^1.999 and multiplication in n(log n)^0.999 have sparked debate.
- Skeptic (srchvrs): Shaving small constants off known exponents may just be a hack. Past asymptotic improvements with galactic constants never mattered practically — if a 2x speedup requires 10^10 more compute, it's useless in a world of finite resources.
- Counterpoint (thomasahle): Worrying that math is "all square packing" underneath misses the point — an ugly result usually just means you picked the wrong perspective.
- The thread captures the classic tension between theoretical algorithm improvements and practical utility.
More from Research
- COLM'26: MathDuels self-play benchmark co-evolves difficulty across 19 frontier models — AI4Code · 2026-10-08
- Apple's Stepped MoE: one model scales 1-4B parameters, beating dense counterparts — apple · 2026-10-08
- Apple-style compression: LSP learns which subspaces to drop, cutting LLM weights 70% — Massimo Bini · 2026-10-08
- Cisco ships VLoc Bench: 500 real vulnerabilities to test if AI agents can find buggy code — aminkarbasi · 2026-10-08
- ByteDance Seed Paper Explains Phase Blind Spots in KV Compression Behind DeepSeek's Erratic Long- Context Performance — teortaxesTex · 2026-10-08
- VeriSoftBench: repo-scale Lean 4 verification benchmark, best LLM scores just 41% — xiye_nlp · 2026-10-08