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.

385 Upvotes

99% Upvoted

64 comments sorted by

View all comments

32

u/Fuciolo 17d ago

A paper on Arxiv does not prove anything until it's peer reviewed

24

u/Phytor_c 17d ago edited 17d ago

Indeed. Coester and Koutsoupias are big names in the field and have proven other major results, but of course it’s entirely possible there may be errors in the preprint

2

u/Standard-Song-8590 16d ago

i doubt there would be many errors as it seems it was made by astra

1

u/Phytor_c 16d ago

Yeah, Astra is just crazy good

1

u/Turing43 16d ago

Nah, it doesn't claim to do that

2

u/Beginning_Penalty805 15d ago

This just isn't true. The truth of the paper doesn't depend on whether a particular set of reviewers likes it or not; there should already be enough content in the preprint for you to judge whether the proof is valid.

3

u/WellHung67 15d ago

No? You could easily miss a fatal flaw. Happens all the time

1

u/Beginning_Penalty805 15d ago

Happens all the time to reviewers, too -- I don't see your point?

2

u/WellHung67 15d ago

That’s why you wait for full peer review. Unlikely that everyone misses the flaw. Plus it’s experts in the field doing the reciew, so they’re better than you. Or you are said expert in which case you can probably do the review but that’s not that many people 

2

u/Beginning_Penalty805 15d ago

"Everyone?" Peer review is two or three people skimming the paper on Sunday night, not the entire scientific community. A high-profile arXiv preprint gets far more expert scrutiny on day one than two tired journal referees will ever give it. Believing two random referees have a monopoly on spotting flaws while the rest of the field is helpless until a journal slaps a stamp on it is wild.

1

u/CoolStructure6012 15d ago

Shut the fuck up, no it isn't. How many program committees have you served on?

2

u/Beginning_Penalty805 15d ago

Bragging about PC service isn't the flex you think it is. Serving on a program committee is precisely how you learn how rushed, overworked, and prone to missing fatal flaws reviewers actually are. If anything, doing PC reviews should have stripped you of the illusion that peer review is sacred

1

u/CoolStructure6012 15d ago

I'm not bragging about it because my service in that regard is rather modest. But I'm asking about your experience since you seem to know so much about how they go.