alt Hacker News> We give a deterministic algorithm that multiplies two n-bit integers in O(n (log n)^(1−κ)) worst- case time, with κ = 2^(−182).
LMAO, I don't think I ever saw such a small number in a CS result.
Replies
I am fully braced for it to be a https://en.wikipedia.org/wiki/Galactic_algorithm
Very surprising result though! Multiplication is easier than sorting.
It fascinates me that there's something like this in something as solid and rigid like matrix multiplication. What causes something so rigid to break apart and "leak" at very large scale? Why does the "optimization" appear to be very, very small? Why does galactic algorithm exists? I can't imagine long division suddenly breaking apart after a billion digit, the structure seems very stable? I have heard before that matrix multiplication is apparently optimize-able at very, very large scale.
Does anyone have an intuition to what causes it? What happens at these large scale (or very small)?
Yeah its ridiculously small, but any improvement on n log n is wild.
Like there is somehow redundancy in a fourier transform that makes it sub Linearithmic?
Which low and behold ->
130. Fourier transforms below n log n.