k-server Conjecture Proved, Closing a Classic Online Algorithms Open Problem
minilek · x · 2026-09-15
Theoretical computer science saw a burst of classic open problems fall in a single day. Aaroth listed several resolved that day:
- k-server conjecture: Christian Coester, Elias Koutsoupias and Marek Zbysiński posted The k-server conjecture is true, proving that a deterministic online algorithm achieves competitive ratio k on every metric space — specifically, the work function algorithm.
- Matroid Secretary
- Matrix Spencer (possibly a few weeks earlier)
The proof represents the work function as a matrix encoding all feasible paths to a configuration; the min and addition operations in optimal costs map to addition and multiplication of formal expressions, and each work function value is the determinant of k columns. A request arrival updates the representation via a change of basis and row replacement, with amortized analysis via a potential function over a larger matrix.
Aaroth's takeaway: we are moving toward a world without open problems, but math isn't going away — interesting work will shift to discovering new questions and coherent theoretical frameworks, while well-defined, agreed-to-be-interesting problems won't last long.
Related event: Decades-Old k-Server Conjecture Proven on arXiv(3 posts)→
More from Research
- Tencent unveils Hyra 2.0, a research agent that builds reusable scientific tools — TencentHunyuan · 2026-11-02
- General Reasoning explains how to train agent swarms with RL and latency pressure — rosstaylor90 · 2026-11-02
- Mathematician Tony Feng: current-paradigm LLMs lack the diversity of thought research needs — littmath · 2026-11-02
- Measure Theory vs Probability: 'You're Confusing the Finger With the Moon' — LucaAmb · 2026-11-02
- DStill Distills Multi-Step Denoising Into One Pass, 6.45x Speedup for Diffusion Speculative Decoding — LucaAmb · 2026-11-02
- Radial gate objective cuts diffusion transformer FID from 16.24 to 11.83 — Junha Park · 2026-11-02