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
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). The authors designed the potential function and proved k = 3 without AI. ChatGPT 6 Astra then 'derived an algebraic proof of correctness for any k', which the authors adapted and revised.
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
Science result
- Field
- computer-science / online algorithms / competitive analysis
- Problem
- k-server conjecture (open since 1988)
- Result
- Deterministic k-competitiveness of the work function algorithm on every metric space.
- AI system
- GPT-6 Astra (ChatGPT), ChatGPT 5.5 Pro, Gemini 3.1 Pro
- Human role
- Human-designed potential and k = 3 proof; the AI generalised it to all k; humans adapted and verified the final proof
- Verification
- Preprint; not peer-reviewed
- Status
- pending
- Why surprising
- A 38-year-old central conjecture of theoretical computer science was finished when a model generalised a human proof from 3 servers to k.
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.
Changelog
- 2026-09-30: created
Related events
- OpenAI releases GPT-6 Astra, its first GPT-6 model ★★★★★
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
Sources (2)
- paperarXiv 2609.15979: The k-server conjecture is true (Coester, Koutsoupias, Zbysiński)
- discussionHacker News discussion
id: 2026-09-14-k-server-conjecture-proved · updated 2026-09-30 · open in the interactive timeline