The k-Server Conjecture Is True: A 30-Year-Old "Holy Grail" Falls
A paper on arXiv (submitted Sept 14, 2026) by Christian Coester, Elias Koutsoupias, and Marek Zbysiński proves the k-server conjecture: "a deterministic online algorithm can achieve competitive ratio k on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it." The proof technique is novel — the work function is represented as a matrix where "each work function value corresponds to the determinant of k columns of the matrix," with a potential function built from a larger matrix for the amortized analysis. The problem, per the paper's own intro: k servers sit in a metric space, requests arrive online, an algorithm must move a server to each request without knowing the future, minimizing total travel; the conjecture (open for ~30 years) says you can always stay within factor k of the offline optimum. WhitneyLand: "This is an important result, sometimes called the holy grail of competitive analysis."
The HN thread (80 pts) did its usual two things well. First, the ELI5 that actually works — FabHK's hot-dog-vendors-in-a-stadium analogy: k vendors serve randomly hungry customers as requests arrive, and the theorem says even against "an evil genius planning the sequence of requests," the online algorithm's total distance is "at most k times higher" than the perfect-foresight optimum. Second, the AI angle, which is where the interesting epistemology lives: "It appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy" (jdw64) — the proposer/verifier split ("External graph state/rudimentary planner + LLM proposer + cheap verifier gets so much done," porridgeraisin), with the counterexample from Knuth's recent experience: "The opposite can happen too... The system suggested an unusual approach that he explored" (gumby). One thread regular fofoz on the stakes: "The proof of the WFA algorithm's (2k-1)-competitiveness for this problem was one of the papers I spent sleepless nights poring over during university."
Why it matters: beyond the CS-theory milestone (the work function algorithm — known since the 90s to be (2k-1)-competitive — is now optimal, you can't do better than k), the thread is a live specimen of how theory communities metabolize AI-assisted mathematics: not "AI proved it," but AI as search-amplifier inside a human verification loop — the same pattern Goodhart's Law Hits the Professions: "AI is breaking our proxies for expertise" describes as the field's new normal.