The k-server conjecture is true
iamsyr
102 points
35 comments
September 15, 2026
Related Discussions
Found 5 related stories in 89.5ms across 6,718 title embeddings via pgvector HNSW
- Dinitz-Garg-Goemans conjecture is false bifftastic · 12 pts · July 22, 2026 · 51% similar
- Jacobian conjecture is false (with help of Fable) k2xl · 30 pts · July 20, 2026 · 47% similar
- A digestion of the Jacobian conjecture counterexample jeremyscanvic · 229 pts · July 21, 2026 · 43% similar
- Qubes OS Security in the Public Record sciences44 · 86 pts · July 18, 2026 · 43% similar
- AI solves 20 year old conjecture in graph theory never_giveup · 15 pts · July 20, 2026 · 42% similar
Discussion Highlights (6 comments)
gwt4life
Explain to me like im 5.
jdw64
Wow, so AI can actually help with difficult problems like this. If that's really true, I mean. Lately I've been feeling that the ability to choose the right problem matters a lot. It's a game where the people who use AI to stake out these problems first have the advantage—so of course the people who were sustained by scientific discussion and community knowledge transfer would feel sad about it, right? But it's really fascinating.
jdw64
Looking at the recent discussions on Hacker News about AI solving difficult problems, it seems there are specific types of mathematical challenges where AI truly excels. It appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy. In particular, AI feels very strong in matching-type problems, almost like fuzz testing. As seen in Terence Tao's conversations, it has a massive advantage in rapidly substituting and testing various models. Given these strengths, I feel it would be highly effective for problems like the Hadamard matrix of order 668, the Lonely Runner conjecture, and the Graceful Tree conjecture. Perhaps the unsolved problems I mentioned will be cracked in the near future? It is fascinating.
JohnKemeny
> The second author, Elias Koutsoupias, dedicates this work to his constant friends Amos Fiat, Anna Karlin, and Christos Papadimitriou. I wonder what Papadimitriou thinks about getting dedicated LLM generated proofs.
fofoz
What memories! The proof of the WFA algorithm's (2k-1)-competitiveness for this problem was one of the papers I spent sleepless nights poring over during university. I am truly thrilled to see the k-competitiveness conjecture resolved!
WhitneyLand
This is an important result, sometimes called the holy grail of competitive analysis. One way to think about competitive analysis is bulk discounts. In life we’re constantly having to choose between quantity and discount. We could buy 1 item for a higher price, or say quantity 5 or 10 to get better discounts. The problem comes when we don’t know in advance exactly how many we’re going to need. What should be our strategy for choosing how many to buy, and whatever the strategy is how well does it compare with having perfect knowledge upfront?