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: k-server Conjecture Proven in Theoretical CS Breakthrough(2 posts)→
More from Research
- TabPFN-3.5 launches with SOTA on complex tabular data, up to 6x faster inference — FrankRHutter · 2026-09-15
- Google's AI-in-science study mines 15M Gemini interactions, 2,600 models and 600-scientist survey — danielrock · 2026-09-15
- Digital fruit fly brain with 166,000 neurons goes viral playing Minecraft and trading bitcoin — 404 Media · 2026-09-15
- EMNLP paper: LLM benchmarks test if answers are right, not how they're framed — IAugenstein · 2026-09-15
- Liquid AI open-sources 'antidoom' FTPO training to fix small-model doom loops — helloiamleonie · 2026-09-15
- Ataraxis Debuts Causal AI That Predicts Cancer Treatment Outcomes Zero-Shot — multiply_matrix · 2026-09-15