alt Hacker NewsThe k-server conjecture is true
Comments
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!
> 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.
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.
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.
[flagged]
[flagged]
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?