The k-server conjecture, the ‘holy grail’ of online algorithms, is proved at Oxford
ChatGPT 6 Astra generalised the authors’ k = 3 proof to all k
Awaiting review
Importance: major (4 of 5)The takeaway
Christian Coester, Elias Koutsoupias and Marek Zbysiński (Oxford) posted a proof of the k-server conjecture (Manasse–McGeoch–Sleator, 1988): the work function algorithm is k-competitive on every metric space (arXiv 2609.15979, 14 Sep 2026).
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 30 September 2026
Your AI and this story
- GPT-6 Astra137 days after its cutoff
- Claude Opus 5.576 days after its cutoff
- Gemini 4 Hydrogen167 days after its cutoff
- Grok 4.7106 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 76 days before it.
Key facts
- The k-server problem was introduced by Manasse, McGeoch and Sleator in 1988; the paper notes it has repeatedly been called the ‘holy grail’ of competitive analysis
- Previous best: the work function algorithm is (2k−1)-competitive (Koutsoupias and Papadimitriou, 1995); the conjecture asks for ratio k
- New proof: represent the work function algebraically as a matrix whose column determinants encode work-function values; the amortised analysis uses a potential defined on a larger matrix of coordinate pairs
- AI role (acknowledgments): the k = 3 potential and ‘initial proof for three servers … was obtained without AI assistance’; discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro gave ‘a deeper understanding of the potential’; ‘ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for any k’; the published proof adapts it, and Astra helped draft some sections
- Discussed on Hacker News (106 points, 15 Sep 2026)
- Status: preprint, not peer-reviewed
What happened
The Oxford team first found a new potential function that proved the open three-server case by hand. After refining it in conversations with ChatGPT and Gemini, they gave the reformulation to ChatGPT 6 Astra, which produced an algebraic proof for all k. The authors then recast that proof in a more natural matrix representation.
Why it matters
The k-server conjecture is one of the best-known open problems in algorithms, and Koutsoupias co-proved the previous best bound in 1995. Here the AI’s contribution is the generalisation step that turned a special case into the full theorem.
What is disputed or not yet verified
| Verification | Preprint; not peer-reviewed |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 1 primary, 1 reaction
Primary
Reactions
- Hacker News discussionnews.ycombinator.com, discussion
Changes
- Filed