A Faster Shortest Path Algorithm

swiftcoder

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

sashank_1509

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

EdSchouten

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

danbrooks

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

throwway262515

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