Fortnow asks when algorithmic results are plausibly optimal, from Metric TSP to matrix mult
fortnow · x · 2026-10-26
Complexity theorist Lance Fortnow writes on when a result is plausibly optimal. Metric TSP's 1.5-approximation (Christofides/Serdyukov, 1976) was long assumed optimal, with attempts to tie improvements to P=NP — until Karlin, Klein, Gharan and Oveis proved a 1.5−1/10^36 approximation in 2020; Klein conjectures 4/3 is the real bound. He contrasts this with matrix multiplication's exponent ω, noting definitional subtleties (a least exponent may not exist) and the contrast between "pretty" and "ugly" runtimes. The lesson: a number being "pretty" is no evidence of optimality.
More from Research
- DeepSeek 1017 checkpoint lands on FrontierCS 2 with a small score jump — scaling01 · 2026-10-26
- Baidu's LeWAM paper added its name 17 days after submission, right after rival LeWAM papers appeared — randall_balestr · 2026-10-26
- RAVEL: training 210 MLLMs to build a strong baseline for picking vision encoders — jiqizhixin · 2026-10-26
- Tencent open-sources WeVisOne-VL: one VLM for detection, OCR, segmentation and matting — lmoroney · 2026-10-26
- Microsoft's Baym: computation is nowhere near brute-forcing biology — KevinKaichuang · 2026-10-26
- MIT paper uses LLMs to measure ambiguity in laws and AI constitutions, EMNLP 2026 Oral — sebkrier · 2026-10-26