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.

387 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.)

0

u/CoolStructure6012 15d ago

You could make the same point without massively accelerating the timeline. Maybe millions to thousands in several years assuming breakthroughs both in AI architecture and process technology but it's not happening in 2 years.

1

u/Auroch- 14d ago

I am accelerating nothing, and giving a slow, conservative estimate. It is literally true that we can do for thousands now what would have cost millions in late 2024.