A Faster Shortest Path Algorithm

A Faster Shortest Path Algorithm(vals.ai)

34 points by leumon 12 hours ago | 9 comments

swiftcoder 11 hours ago |

If I'm reading correctly, this is one of those theoretical improvements that doesn't put a whole lot of practical speedup on the table. But I do wonder how many other algorithms in computer science are going to see their bounds fall in the next few months

throwway262515 4 hours ago |

> For instance, if n = 2^1000, the ratio of the leading expressions n lg n and n (lg n)^(11/12) is 1000^(1/12) ≈ 1.78, ignoring constants and lower-order terms. This is not a measured speedup.

Isn't it likely that the constant factor slowdown of an apparently more complicated algorithm will dominate 1.78?

> The constants in the formal construction are enormous, so this does not establish a practical speedup.

A pity the author stopped here.

EdSchouten 11 hours ago |

The time complexities given in this article would be easier to read if they used |V| and |E| instead of m and n.

sltkr 11 hours ago | |

It's extremely common in graph theory to use n and m to mean vertex and edge count respectively. And if you're unfamiliar with graph theory, the notation |V| or |E| is hardly more intuitive, especially if you're not an English speaker.

sashank_1509 11 hours ago |

I don’t want to rain on the parade here, but this is a typical issue with AI slop maths or CS. It just builds complexity upon complexity to generate diminishing improvements (this case doesn’t lead to any practical speedup). This has been my experience in code, and also been my experience in limited Maths I know.

I think a reasonable conclusion now that AI is getting better than us humans at this, is that humans should stop doing this. I think there are strong reasons that humans should never have been doing this in the past but now it’s far more clear, AI will out complicate whatever complexity you can build and then beat at you at its handling of intricate complexity.

Humans should focus on finding simple solutions that lead to a 10X improvement. AI rarely does this, though I have noticed it some times doing this in maths, but this was the case when the solution was already present in some distant literature and no human had the expertise in 2 distant areas to make the connection. When AI does this, it is a welcome advancement, and hopefully the bridge it shows leads to exciting new developments.

But LLMs rarely do this, and I think humans should exclusively focus on this, because it seems like we are far better than LLMs at keeping things simple and finding new insights that leads to 10X, 100X improvements

highway900 9 hours ago | |

This is a good take on the situation. LLMs are able to achieve the 1000 monkey problem by throwing inexhaustible amounts of resources at the problem. But novel solutions to problems seem to be scarce. There are many things in the world that can be done using complex processes but the ones that survive are those that are easy to understand and replicate. A good example of this is the production of carbon nano tubes or solid state batteries. Neither have an easy to understand and scalable solution yet. Both seem like “make the world a better place” technologies that are not coming from any frontier lab.

usrnm 10 hours ago | |

> Humans should focus on finding simple solutions that lead to a 10X improvement

How many humans can you name who really did that? Like, in the whole history of our species

danbrooks 10 hours ago |

I'm confused.

This seems to imply that they used Claude Opus 5.5 before it was released on September 22nd.

mdspan 8 hours ago | |

Companies frequently get early access to frontier models.