Breakthrough Tracker record
A preprint claims the optimal deterministic k-server bound
Coester, Koutsoupias and Zbysiński claim that the work-function algorithm is k-competitive on every metric space, matching the general lower bound and resolving the deterministic k-server conjecture.
← Back to the filtered Breakthrough Tracker
- Stable ID
cs-k-server-conjecture-work-function-2026- Revision
cs-k-server-conjecture-work-function-2026.v1- Field
- Theoretical computer science · Online algorithms and competitive analysis
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Provisional · Provisional claimed proof
- Last checked
AI role
The authors report that ChatGPT 6 Astra derived the arbitrary-k algebraic proof from a human k=3 potential and adapted it to their representation; the authors revised and checked the proof. Other models and Oxford ARC were used in exploration and checking.
Record details
- Problem or result
- The deterministic k-server conjecture for online algorithms
- Authors
- Christian Coester, Elias Koutsoupias and Marek Zbysiński
- Institutions
- University of Oxford
- Result date
- First-version preprint submitted September 14, 2026
Why it matters
The conjecture has been central to competitive analysis since the late 1980s. The claimed k ratio improves the longstanding general 2k−1 work-function bound to the conjectured optimum.
Limits
This is a first-version preprint. No peer review, formal proof or independent semantic correctness assessment was located; author-page repetition and machine-generated reviews are not independent validation.
Sources
Correction and revision history
- 2026-10-02 — Added after primary-source, scope, status, AI-role and limitation review.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.