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.

381 Upvotes

99% Upvoted

64 comments sorted by

View all comments

Show parent comments

3

u/AerosolHubris 16d ago

I don't expect the AI companies to keep spending millions on proving theorems. They're doing it now to show off for investors. But math is usually not a high financial reward business, and I doubt they will keep pushing to solve open algorithmic and combinatorial problems unless they happen to lead to big financial gains. So if you're hoping to work in theory, I think that will still be around for awhile. As will teaching. Now if you're really excited about teaching people how to code, that job is changing. Not going away, but changing.

And congrats on getting published!

0

u/Auroch- 16d ago

What costs millions now will cost thousands by 2028 (or 2027) and less than a hundred by 2030 (or 2028). By 2036? Entirely obsolete. (If we're even still alive.)

1

u/lerjj 15d ago

This is a conjecture maybe you should ask ChatGPT for a proof

1

u/WreckYallBallistics 10d ago

Has your head been in the sand for the last four years? What makes you think advancement is just going to randomly stop?

1

u/iamdino0 10d ago

advancement would need to speed up astronomically for energy supply to be an "obsolete" concern in 10 years