k-server conjecture proven true: work function algorithm achieves competitive ratio k
ctjlewis · x · 2026-09-16
A new arXiv paper by Christian Coester, Elias Koutsoupias, and Marek Zbysiński proves the long-standing k-server conjecture: a deterministic online algorithm can achieve competitive ratio k on every metric space. The proof uses the work function algorithm, representing the work function as a matrix where feasible paths map to formal expressions and each value corresponds to a determinant of k columns; requests update the representation via change of basis and row replacement, with amortized analysis via a potential function on a larger matrix.
Related event: Decades-Old k-Server Conjecture Proven on arXiv(3 posts)→
More from Research
- Radial gate objective cuts diffusion transformer FID from 16.24 to 11.83 — Junha Park · 2026-11-02
- REA: async brain-cerebellum runtime for robots where policies never wait on the LLM — Pengfei Zhou · 2026-11-02
- Microsoft's MemSteer turns unlabeled user histories into agent memory supervision — MicrosoftResearch · 2026-11-02
- SciGame benchmark uses counterfactual worlds to expose LLM agents' priors vs evidence — Yusheng Zhao · 2026-11-02
- On Terence Tao's blog, Frank Calegari calls on mathematicians to adapt after OpenAI's 700-paper release — Hesamation · 2026-11-02
- Tsinghua & Microsoft's HarnessMM cuts agent token use by up to 87.93% while raising success rate — rohanpaul_ai · 2026-11-02