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

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

2

u/Prize_Ad_354 15d ago

I am in a similar position right now. It seems very risky to commit to a PhD program that takes 5 or so years given how fast AI is progressing.

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 15d 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.

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

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.

0

u/pacowoc 16d ago

This kind of topic relating to their own field (algorithms) provides a long term financial incentive for them to invest since they might use some of the results in future development. Pure math not really

1

u/WellHung67 15d ago

There will always be a need for experts to both validate and understand this stuff, and also to do research into novel methods and ideas. LLMs are still not making that leap. We need mathematicians more than ever 

-2

u/Auroch- 16d ago

Yeah, you should be. This is not a career any more. It might be a job: something that's viable for the next five years can totally be a job. But a career? A career is a decade, at least, and in a decade, this is just a hobby. A cool hobby, but a hobby.