k-server conjecture proven as multiple open CS problems fall in weeks
naval · x · 2026-09-15
A new arXiv paper The k-server conjecture is true proves the k-server conjecture: a deterministic online algorithm can achieve competitive ratio k on every metric space, via the work function algorithm.
The proof uses an algebraic matrix representation of the work function encoding all feasible paths; min/addition in optimal costs map to multiplication/addition of formal expressions, each work function value corresponds to a determinant of k columns, and requests update the representation via change of basis and row replacement. The amortized analysis rests on a potential function over a larger matrix of coordinate pairs.
The buzz follows several open problems falling in quick succession (k-server, Matroid Secretary, Matrix Spencer). Commenters argue we're moving toward a world without open problems, but math lives on: interesting work will shift to discovering new questions and coherent theoretical frameworks.
Related event: k-server Conjecture Proven in Theoretical CS Breakthrough(2 posts)→
More from Research
- First UMI dataset collected: faster capture than tele-op, but mimicking robots is exhausting — DominiqueCAPaul · 2026-09-16
- Epoch AI: GPT latency curves bend at long context while Claude stays linear — krishnan · 2026-09-16
- ApprenticeBench: best human testers pass only 51% first-try — agents don't need perfection — hhsun1 · 2026-09-16
- New Paper: Adding RL After OPD Consistently Beats Pure OPD, Pure RLVR, and Joint Methods — gregd_nlp · 2026-09-16
- Retinal imaging AI detects atrial fibrillation risk years early in ~90,000-person study — EricTopol · 2026-09-16
- First double-blind eval of a proprietary model using a private benchmark ships — KLdivergence · 2026-09-16