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!
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?
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.
It's honestly just good at math. Even at theory building i wouldn't put it below 90 percentile. Just on some things it's superhuman already and some not yet.
> appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy.
The opposite can happen too, as Knuth’s recent experience showed. The system suggested an unusual approach that he explored.
Yes, LLM is excellent at optimizing exhaustive search algorithms into "representative" search algorithm, by generating heuristic classifications at high scale.
It sounds like the same class of application as vulnerability finding: try a million dumb things, and one of them can work. No human would try all one million, but a big enough computer can.
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?
I didn't understand it either, but now given the sibling posts I'll give it another shot:
Assume you have a number of hot dog vendors in a stadium, and over time randomly people get hungry and want a hot dog. One of the hot dog vendors needs to come to them, covering a certain distance, and "serve" them their hotdog. (After that, the vendor will idle around there.)
Assume there is a central controller with a radio that oversees the whole thing, noticing requests, then picks a hot dog vendor when a request comes in and sends them on the way. After the game, all the hot dog vendors together walked a certain distance: that's the cost (which of course you'd like to minimise).
Crucial question now is which hot dog vendor to pick for each request, and there are many algorithms (you could always pick the closest one, for example).
However, now comes the trick: Suppose the controller knows in advance all the requests - who will want to have a hotdog when and where. He still, anytime a request comes in, needs to pick a vendor to send them to the request. But now, knowing the entire future, the controller can make better choices, leading to a smaller total cost. (That's the offline version; getting to know the requests only "as they come in" is the online version.)
The question now is: Compare the actual cost an "online" algorithm incurs with the "super optimal" that would have been feasible with full foresight ("offline"). It was proven that, for k hotdog vendors, it is at least k times higher (that's the "competitive ratio") worst case (plus a constant). On average, the online algo can do much better, but worst case it would be at least k times worse.
Here, the authors of the paper prove the conjecture, namely that it is also at most k times higher. (So, even if an evil genius plans the sequence of requests against this algo, it can't make it more than k times worse.)
It's not really like you're 5, but the third sentence of the introduction makes it really understandable:
> The problem’s definition is simple: There are k servers located at points of a metric space. At each time step, a request arrives at a point of the metric space. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests. The goal is to minimize the total distance traveled by servers.
So metric space is anything where you can measure a distance, so you know the distances between all servers and the distance from the request to all servers. Could be direct distance, could be travel time …
Easiest to just imagine just some (eg. n=5) servers on a plane. A request pops up somewhere on the plane. Which server do you move there, such that the total distance moved by servers is as low as possible in the end after a sequence of requests.
Fair enough, but the abstract really is too opaque imo.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.
I was like "algorithm for what?" when I knew what every one of those terms meant. Lots of things use k servers. Lots of problems involve metric spaces.
I feel like the paper itself does a fairly good job:
> The [k-server] problem’s definition is simple: There are k servers located at points of
a metric space. At each time step, a request arrives at a point of the metric space. An online
algorithm must serve the request immediately by moving a server to the requested location, without
knowledge of future requests. The goal is to minimize the total distance traveled by servers.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive
ratio k on every metric space.
I only had to look up what "competitive" means in this context, and wikipedia [0] had this to say about it:
> An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
The ratio by which this performance is bounded for a k-competitive algorithm is k (plus some constant) [1]. We can consider the analogy of k support technicians ("servers) located in different (physical) locations ("in metric space"): The conjecture/theorem states that in any metric space (Not necessarily two- or three-dimensional), there exists an online algorithm that results in travelled distances of no more than roughly k times that of the optimal distance if all requests were known in advance.
I’d be shocked if anyone with any kind of post-secondary education in any numerate discipline couldn’t give you at least an informal definition of a metric space. Certainly all the physicists, all the geneticists, all the ML people.
I should have added "for a technical paper". They are generally not written for five year olds, and "metric space" is a term I've seen introduced anywhere between semesters 1 and 3 in most technical Bachelor's degrees.
I take ELI5 in hackernews comments to mean: "Explain like i'm someone with a vaguely technical background but no knowledge in this particular field", not "I'm a literal five year old". I think it's probably close to impossible to explain this adequately to an actual five year old while staying true to the essence of the paper.
I would expect someone commenting ELI5 on Hacker News to mean that they didn't understand the article directly, so pasting several paragraphs verbatim is not particularly helpful to them. If you think that the article is clear, and they're still asking for clarification, it's a sign that you've probably overestimated the clarity to someone with less experience in the subject (as always, relevant xkcd for this: https://xkcd.com/2501/)
That's fair, I had assumed they hadn't read the article at all ;) If they have, it would have been nice to know which parts of the problem definition the paper describes as "simple" they struggled with, otherwise I default to "I haven't read the article and would like a summary for a technically inclined layman"
I would expect someone who says ELI5 to have found pretty much all of it hard to understand. The paper calling something "simple" is either them talking to other experts or an instance of the same phenomenon I called out where experts vastly underestimate how approachable things are to non-expert. At least personally, I had never heard the term "metric space" before. I assumed it didn't mean "three dimensional space measured in units that are an exponent of meters", but I didn't know how to tell the difference between whether it was a specific nuanced mathematical concept or if it just meant "space that can be measured". I could google it, but when I have to do that before I've gotten through the first sentence that the paper describes as "simple", it does not give me any confidence that the paper is written with an audience like me in mind.
I wonder what Papadimitriou thinks about getting dedicated LLM generated proofs.
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?
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.
Solved? https://epoch.ai/frontiermath/open-problems/hadamard
The opposite can happen too, as Knuth’s recent experience showed. The system suggested an unusual approach that he explored.
External graph state/rudimentary planner + LLM proposer + cheap verifier gets so much done.
But it's really fascinating.
Assume you have a number of hot dog vendors in a stadium, and over time randomly people get hungry and want a hot dog. One of the hot dog vendors needs to come to them, covering a certain distance, and "serve" them their hotdog. (After that, the vendor will idle around there.)
Assume there is a central controller with a radio that oversees the whole thing, noticing requests, then picks a hot dog vendor when a request comes in and sends them on the way. After the game, all the hot dog vendors together walked a certain distance: that's the cost (which of course you'd like to minimise).
Crucial question now is which hot dog vendor to pick for each request, and there are many algorithms (you could always pick the closest one, for example).
However, now comes the trick: Suppose the controller knows in advance all the requests - who will want to have a hotdog when and where. He still, anytime a request comes in, needs to pick a vendor to send them to the request. But now, knowing the entire future, the controller can make better choices, leading to a smaller total cost. (That's the offline version; getting to know the requests only "as they come in" is the online version.)
The question now is: Compare the actual cost an "online" algorithm incurs with the "super optimal" that would have been feasible with full foresight ("offline"). It was proven that, for k hotdog vendors, it is at least k times higher (that's the "competitive ratio") worst case (plus a constant). On average, the online algo can do much better, but worst case it would be at least k times worse.
Here, the authors of the paper prove the conjecture, namely that it is also at most k times higher. (So, even if an evil genius plans the sequence of requests against this algo, it can't make it more than k times worse.)
> The problem’s definition is simple: There are k servers located at points of a metric space. At each time step, a request arrives at a point of the metric space. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests. The goal is to minimize the total distance traveled by servers.
So metric space is anything where you can measure a distance, so you know the distances between all servers and the distance from the request to all servers. Could be direct distance, could be travel time …
Easiest to just imagine just some (eg. n=5) servers on a plane. A request pops up somewhere on the plane. Which server do you move there, such that the total distance moved by servers is as low as possible in the end after a sequence of requests.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.
I was like "algorithm for what?" when I knew what every one of those terms meant. Lots of things use k servers. Lots of problems involve metric spaces.
> The [k-server] problem’s definition is simple: There are k servers located at points of a metric space. At each time step, a request arrives at a point of the metric space. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests. The goal is to minimize the total distance traveled by servers.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.
I only had to look up what "competitive" means in this context, and wikipedia [0] had this to say about it:
> An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
The ratio by which this performance is bounded for a k-competitive algorithm is k (plus some constant) [1]. We can consider the analogy of k support technicians ("servers) located in different (physical) locations ("in metric space"): The conjecture/theorem states that in any metric space (Not necessarily two- or three-dimensional), there exists an online algorithm that results in travelled distances of no more than roughly k times that of the optimal distance if all requests were known in advance.
[0] https://en.wikipedia.org/wiki/Competitive_analysis_(online_a...
[1] https://www14.in.tum.de/personen/albers/papers/brics.pdf Section 1.1
The phrase “metric space” (more or less) disqualifies anyone without an undergraduate degree in mathematics.
Fortunately a sibling to the parent explains that.