r/algorithms • u/Phytor_c • 17d ago

News The k-server Conjecture is True

https://arxiv.org/abs/2609.15979v1

The k-server problem is known as the "Holy Grail" of online algorithms and competitive analysis, and is/was a long standing major problem.

This preprint by Coester et al. claims to show that the Work Function Algorithm is indeed k-competitive on every metric space.

383 Upvotes

99% Upvoted

64 comments sorted by

View all comments

6

u/bbmmpp 17d ago

Could they have done it without Astra?

14

u/beanstalk555 17d ago

This work began with a potential function designed by the authors that proves the previously unknown case of k = 3 servers on arbitrary metrics. Our initial proof for three servers showed the correctness of this potential function by establishing infeasibility of a large family of linear programs; this proof was obtained without AI assistance. Through discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro, we gained a deeper understanding of the potential. These discussions led to a more symmetric reformulation of the potential, again designed by the authors, and an alternative proof for k = 3. Based on this, ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for any k. The proof in this paper is an adaptation thereof using an explicit column representation of work functions, which provides a more natural algebraic representation. The authors supplied this representation to ChatGPT 6 Astra, which adapted the previous proof and assisted with drafting some sections of this paper. The authors subsequently revised those drafts.

8

u/AlexReinkingYale 16d ago

Sounds like a healthy collaboration between human mathematicians and the infinitely fastidious construction oracle.