The k-server conjecture is true

jdw64•about 2 hours ago

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.

pyentropy•about 2 hours ago

> Hadamard matrix of order 668

Solved? https://epoch.ai/frontiermath/open-problems/hadamard

jdw64•about 2 hours ago

wow!

gumby•about 1 hour ago

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

jdw64•about 2 hours ago

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.

gwt4life•about 2 hours ago

Explain to me like im 5.

zygentoma•about 2 hours ago

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.

fxwin•about 2 hours ago

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

fn-mote•33 minutes ago

There’s a difference between “pretty good” and understandable.

The phrase “metric space” (more or less) disqualifies anyone without an undergraduate degree in mathematics.

Fortunately a sibling to the parent explains that.

The k-server conjecture is true

⚡ Community Insights

Discussion (9 Comments)Read Original on HackerNews