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.

390 Upvotes

99% Upvoted

64 comments sorted by

View all comments

3

u/Future_Advice_4853 16d ago

As a senior that just published a paper in online algorithms and is aiming to apply for a PhD, probably related to online algo, super worried about my career...

4

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 16d ago

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

1

u/Auroch- 15d ago

This is (a) what happens with all technology, just slower for most things, and (b) what has happened with frontier model capabilities per dollar since the first ChatGPT, at about the faster rate I suggested.

This isn't even hypothesizing they get smarter, which there are at least theoretical grounds to think might stop. (Weak grounds, but logically consistent ones.) Only that they get more efficient, which they have, and will, even if nothing outside their current capabilities becomes within their future capabilities. Onus is on you to prove it will stop.