A Faster Shortest Path Algorithm | Hacker News Reader

A Faster Shortest Path Algorithm

vals.ai

39 pointsleumon12 comments

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

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

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.

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

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.

> 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

This world has 8.3 thousand thousand thousand humans in 2026. With such mindnumbly vast population, and our feeble primate brains (see Dunbar's number) limiting us to relate to about 150 people, I don't think it's fair to ask for names, intimate or not.

Nevertheless it's certain that there has to be people alive who saw a complex problem and simplified it 10x, even if the solution never got out of their local sphere. Solutions that you and me would implement with automation and sensors, people in developing countries would find a way with less technology or resources. Even our current systems seem needlessly complex and overengineered compared to when hardware was a limitation.

If you want to think about needless complexity being everywhere, take for example the simplicity of the Internet, made when hardware was limited, against modern monstrosities like Bluetooth, now that we can just throw more hardware at problems.

> there has to be people alive who saw a complex problem and simplified it 10x

Absolutely. Let's be generous and say that there are a thousand of them alive today, what about everyone else? Are their lives meaningless now?

> the simplicity of the Internet

The Internet is TCP/IP and TCP/IP is a lot of things but hardly "simple"

99.9% of humanity don’t derive meaning from their work, sad but true. They don’t care if their life has meaning, if their work is actually valuable etc.

HN just selects for the latter who care. Yes it’s probably much harder for those who care to have a meaningful life in the presence of LLM’s unfortunately.

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

I'm confused.

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

Companies frequently get early access to frontier models.

Reply on news.ycombinator.com