In the end of video they tell there is no way that any implementation of their algorithm gets close to beating existing algorithms in the real world.
https://cacm.acm.org/research/almost-linear-time-algorithms-...
On a similar note, there's a lot of work put into optimal matrix multiplication algorithm. We know the lower bound is N*2, the obvious upper bound is N*3, the best (complexity wise, not practical at all) current algorithm is N*2.37, but we don't know how fast can it really get. Is it possible to write N*2 algorithm? We don't know.
> Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.
Are there examples of Galactic Algorithms that now aren't Galactic Algorithms?
edit: turns out some matmul algorithms are?
From O(mn) to O(m) ... thus excluding N (number of vertices) from computation ...
Too good to be true?
Still, a neat theoretical result.
TFA didn’t describe Kyng’s breakthrough in terms of this mscore it considers so important. What’s up with that?
https://news.ycombinator.com/item?id=31675015 (72 comments)
https://cacm.acm.org/research/almost-linear-time-algorithms-...
o(n) seems like a stronger statement to me than O(n), since all o(n) algorithms are O(n), but the reverse is not true.
Also if o(n) applies to all n, however small, whereas O(n) applies only when n -> inf,
(From the Wikipedia page example: 2n = O(n) but 2n != o(n))
Then doesn’t that means this algorithm should be applicable to even small n’s? Then it would be the opposite of a galactic algorithm, as someone above suggested, wouldn’t it?
Or am I missing something?
lim (n -> infinity) f(n)/g(n) = 0
For instance, this function is o(n), because 1e1000/n goes to 0 as n grows.
f(n) = 10**n if n < 1000 else 1e1000
* Ps, if memory serves me correct, 3↑↑64 is Graham's number.
In other words, it's an algorithm scheme that allows you to get an algorithm running in time O(m^ɛ) for any ɛ>1.
I'm not asking for help decoding the notation; I'm asking for if anyone knows what the more detailed bound is that O(m^(1+o(1))) is abstracting.
Both are fascinating problems, but quite different. Finding shortest paths was typically solved with Dijkstra's algorithm [1], until someone discovered an amazing optimization scheme by precalculating some information that speeds up the search algorithm dramatically [2]. Thanks to this breakthrough, one can now interactively drag routes on Google Maps, for instance. And have Rome2Rio.
Solving a problem for computational efficiency is pointless.
Wy
Take a look at AI neural networks where they blast computational resources.
May be
One day this might help.
Reply to myself
Appreciate this post. And get back to writing.
Appreciation
Out of so many other less interesting post, this post caught my attention and nowhere it spoke about how it works, most importantly why it is needed.
Preprint at https://arxiv.org/abs/2203.00671
(Pages 68-75 build up the full details of the bound, which looks something like Õ(mκ⁻²α⁻²ϵ⁻¹). There are enough details over the preceding dozens of pages that I can't tell at a glance exactly what all the variables stand for.)
Technically this captures any logarithmic factors, such as exp(O(log^(7/8) m log log m)) as presented on page 75).
The constant factors are currently so large that even multiple orders of magnitude speedups would not make this practical.
Fortunately, in many cases, even when the detail is omitted from the headline theorem, they did in fact do the work and it is in fact stated lower down in the body of the paper; or in other cases they fail to state it but it can be easily assembled from a few parts. That's why I was asking.
But sometimes though it's a big complicated thing and they were just like, eh, let's not bother figuring out exactly what it is. To which I say, laziness! You're just making other people do a proof-mine later! You're doing this much, do the work to get a concrete bound, because you can do it better than later proof-miners can!
I won't say that in an ideally functioning mathematics proof-mining would never be necessary, that'd be like saying that in a well-written mathematics one would never need to refactor, but c'mon, mathematicians should at least do what they can to reduce the necessity of it.
It comes from directly applying the definition of matrix multiplication on a square matrix.
Being worse on purpose is always possible, but it doesn't change that bound.
It's the "obvious" upper bound, not the "how did you even get here without noticing the obvious method" upper bound.