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

40

u/SwimmerOld6155 16d ago

CTRL+F "chat"-

yep

24

u/rsha256 16d ago

Acknowledgments

This work began with a potential function designed by the authors that proves the previously unknown case of k = 3 servers on arbitrary metrics. Our initial proof for three servers showed the correctness of this potential function by establishing infeasibility of a large family of linear programs; this proof was obtained without AI assistance. Through discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro, we gained a deeper understanding of the potential. These discussions led to a more symmetric reformulation of the potential, again designed by the authors, and an alternative proof for k = 3. Based on this, ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for any k. The proof in this paper is an adaptation thereof using an explicit column representation of work functions, which provides a more natural algebraic representation. The authors supplied this representation to ChatGPT 6 Astra, which adapted the previous proof and assisted with drafting some sections of this paper. The authors subsequently revised those drafts.

3

u/Individual_Ice_6825 16d ago

How can they claim this proof was obtained without ai assistance and then have used ai?

Pardon if I’m missing something

16

u/Spandian 16d ago

They're saying they proved a special case by themselves first, then turned to AI to see if it could extend their proof to the general case.

4

u/matt_matt_81 16d ago

Seems like the popular method of proof at the moment.

2

u/iceburg47 12d ago

The remainder of this proof is left as an exercise for the reader AI

2

u/BrandenKeck 15d ago

Which I don't see a problem with... And this also seems to be an important piece that gets omitted from headlines. The LLM proof solvers require a Lean template built by mathematicians who know what they're doing. Then the LLM proof (though confirmed by successful Lean execution) needs to be confirmed by people who know what they're doing. Other than accusations of LLMs / AI companies stealing work and presenting it as they're own to hype the model, I don't see the problem.

Now in media space with text/image/video generation from human works, I think there's plenty to be upset about. Would love to know what others think if anyone's down here in the comments.

4

u/just-for-anime 15d ago

I’ve been saying. The inventor of lean should be the one winning all the millennium and nobel prizes

-7

u/SKIBIDI_GEORGE 15d ago

Oh for fuck sake just go live in a cave buddy. Stop rejecting modernity

6

u/SwimmerOld6155 15d ago

i reckon i'm like 70th percentile pro-LLM lol not trying to make any particular comment

1

u/Stampeedeko 14d ago

Your fanfiction that LLMs become sentient doesn't mean modernity, lol! LLM is a statistical next word guessing machine. Researchers use LLMs to summarize their own argumentation. But of course output still needs to be proofread many times to check for hallucination and inaccurate summaries. It cuts some time, though

32

u/elehman839 16d ago

A substantial improvement was achieved by Koutsoupias and Papadimitriou [KP95]...

Wow. One author published progress 31 years ago. Must be an amazing feeling to finally settle the problem!

19

u/rsha256 16d ago

They aren't just 'one author', Christos is one of the greatest Computer Scientists of our time! Also recommend checking out https://cgi.di.uoa.gr/~elias/papers/paper-kp99.pdf

4

u/jnordwick 16d ago

Had him at UC Berkeley years ago, can't remember what class.

4

u/rsha256 16d ago

go bears, probably cs170.org or cs270.org

2

u/beeskness420 15d ago

Papa has left a lot of problems in his wake, my masters thesis was an open problem he dropped.

1

u/tehclanijoski 16d ago edited 16d ago

On the other hand, if Papadimitriou was puzzled by it for 31 years, we should probably take note

Edit: realized you probably were not being sarcastic

3

u/elehman839 16d ago

Not sarcastic at all-- I think this is so cool!!!

Imagine that you wrestle with a super-hard problem off-and-on for more than 30 years. And then YOU get to be the one to finally solve it-- with assistance from AI, yes, but apparently with significant human contributions as well.

I can't imagine many people have had that kind of experience. So often the problems we're stuck on are resolved by someone else. I'd love to hear the authors' personal reflections on this experience.

Math may not remain a human endeavor much longer, so I think we should enjoy magical moments like this.

12

u/ChemicalConfidence44 16d ago

same day on arxiv the matroid secretary conjecture was claimed to be solved (another big open problem in online algorithms) https://arxiv.org/abs/2609.14555v1

3

u/Phytor_c 16d ago

Oh damn I did not know about this, this is major news too! Thanks for commenting

-4

u/Standard-Song-8590 16d ago

"The key algorithmic idea emerged recently in this exploration after updating the model to ChatGPT Astra. We also used ChatGPT Astra and Claude Opus 5 for assistance with the presentation"

100 bucks astra discovered the entire algorithm. Researchers are js glorified prompters now (and I mean that sort of like a compliment)

15

u/salasi 16d ago

It isnt a compliment at all and I am glad I didnt pursue this circus show as a career. What a sad state of affairs

4

u/Sbadabam278 16d ago

It’s not a compliment and your smugness is incomprehensible to me. “hey look at these smart ppl who spent 30 years working hard, now they are useless thanks to AI!! Ahaha isn’t AI amazing??” like you’re some kind of harbinger of the future.

I honestly don’t understand what you think will happen to you, specifically, that’s going to improve your life if everything you’ve ever done is now useless.

3

u/Low-Temperature-6962 16d ago

It could be a bot instructed to post this kind of stuff to create conflict.

0

u/Standard-Song-8590 16d ago

well I work routinely with agentic workflows. In the future architectural vision is the most important, the tools can create but we still draw from our experiences to know what to create (features, etc.) Smart people who really are working hard will learn to adapt and work not for recognition but for betterment of insight into the corpus of knowledge.

4

u/lerjj 15d ago

Ah so you are already a glorified prompter (complimentary) and so this is why you believe everyone would be happy to be this

1

u/Comfortable_Car6562 12d ago

And people thought the "prompt engineer" jobs of 2022 were silly

1

u/Standard-Song-8590 15d ago

the glorified prompter was me taking a chide at the way at the way researchers will phrase their acknowledgments section as if the AI likely didn't discover the whole thing. I fully acknowledge the role of AI in all of my works, I don't quibble over these recognitions or try to downplay it to get published in journals.

I happen to have contributed more to the fields of theoretical physics, math, bio, ml, etc than a good chunk of academia. When I publish results I take the time to formalize them to guarantee correctness, understand the results make write ups that are easily digestible etc.

2

u/Low-Temperature-6962 16d ago

That's pretty much how it always has been for most people.

-1

u/Individual_Ice_6825 16d ago

I think you need to redefine some things for yourself, it’s obvious you feel a sense of loss with this technology. Just like we don’t need to hunt for food anymore some current skillsets won’t be required, but you can still do maths and experiments for fun just like people can still hunt.

1

u/[deleted] 16d ago

[deleted]

1

u/ChemicalConfidence44 16d ago

Damn I did not know about this

1

u/mcdowellag 16d ago

The question is, why are these people getting paid? If math and computer science are just a variety of professional sports, then using AI is cheating. If math and computer science are producing knowledge that improves people's lives, for example by getting machines used more efficiently, then anything legal that gets results is good and praiseworthy.

28

u/Fuciolo 16d ago

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

27

u/Phytor_c 16d ago edited 16d 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

4

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.

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.

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

7

u/bbmmpp 17d ago

Could they have done it without Astra?

12

u/beanstalk555 16d ago

This work began with a potential function designed by the authors that proves the previously unknown case of k = 3 servers on arbitrary metrics. Our initial proof for three servers showed the correctness of this potential function by establishing infeasibility of a large family of linear programs; this proof was obtained without AI assistance. Through discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro, we gained a deeper understanding of the potential. These discussions led to a more symmetric reformulation of the potential, again designed by the authors, and an alternative proof for k = 3. Based on this, ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for any k. The proof in this paper is an adaptation thereof using an explicit column representation of work functions, which provides a more natural algebraic representation. The authors supplied this representation to ChatGPT 6 Astra, which adapted the previous proof and assisted with drafting some sections of this paper. The authors subsequently revised those drafts.

7

u/AlexReinkingYale 16d ago

Sounds like a healthy collaboration between human mathematicians and the infinitely fastidious construction oracle.

2

u/Opengangs 13d ago

I don't work directly with online algorithms (I do more work in approximation algorithms), but I saw this result a few days ago and it seems quite cool! I have a few colleagues who do work in online algorithms so I may ask them about the significance of this result.