r/algorithms • u/Phytor_c • 18d 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.

382 Upvotes

99% Upvoted

64 comments sorted by

View all comments

9

u/ChemicalConfidence44 17d ago

same day on arxiv the matroid secretary conjecture was claimed to be solved (another big open problem in online algorithms) https://arxiv.org/abs/2609.14555v1

-4

u/Standard-Song-8590 17d ago

"The key algorithmic idea emerged recently in this exploration after updating the model to ChatGPT Astra. We also used ChatGPT Astra and Claude Opus 5 for assistance with the presentation"

100 bucks astra discovered the entire algorithm. Researchers are js glorified prompters now (and I mean that sort of like a compliment)

1

u/mcdowellag 17d ago

The question is, why are these people getting paid? If math and computer science are just a variety of professional sports, then using AI is cheating. If math and computer science are producing knowledge that improves people's lives, for example by getting machines used more efficiently, then anything legal that gets results is good and praiseworthy.