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: Decades-Old k-Server Conjecture Proven on arXiv(3 posts)→
More from Research
- Detecting covert instruction-following via internal representations parallels J-space work — dioscuri · 2026-11-02
- Xiaomi MiMo's CodeSpecWeave trains coding agents on interdependent specs for long-horizon coding — XiaomiMiMo · 2026-11-02
- Mistral Large 4 writes a quantum chemistry SCF solver from scratch with one short prompt — MistralAI · 2026-11-02
- Hunting for the most concrete "curing cancer with AI" roadmap of 2025 — iskander · 2026-11-02
- New theory paper proves linear decay is the unique minimax-optimal stepsize schedule for SGD — konstmish · 2026-11-02
- Karpathy's nanochat: the best ChatGPT $100 can buy, near 60k GitHub stars — karpathy · 2026-11-02