Hacker News Reader

Hacker News

Comment by kingstnap | Hacker News Reader

Full thread

kingstnap

Some of these are interesting ngl.

109. Integer multiplication below n log n

Surprising that this is possible.

158. The Euclidean plane cannot be colored with five colors.

Only 6 and 7 remain!

376. Universal computation in forced Navier–Stokes flows.

Morning coffee proven turing complete

View on HN

Integer multiplication is very unexpected, I think most people believed in the n log n lower bound!

Note that these are all preprints. None are verified.

Other than the by the lean certificate you mean.

Lean has bugs & proofs of ⊥ that have gone undetected previously.

many of these are not accompanied with leanslop

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

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 would be absolutely unbelievable if such an improvement were practical.

Then 'n' means kind of different things for sorting vs. multiplication though. For example for sorting we assume constant time comparison, which doesn't make sense inputs of O(n) bits

If you sort n k-bit items for a total time of O(nk logn), that scales more poorly in n than multiplying n-word integers. Of course if k is constant you can do radix sort, but I genuinely don't know under what conditions radix sort is more/less galactic than this multiplication algorithm.

this alg is way more galactic than radix sort. radix sort often wins in the hundreds of elements. the nlogn multiplication requires numbers with more digits than atoms in the universe (although that could probably be brought down a lot)

Ah thanks for pointing this out, for some reason I had always equated radix sort and bucket sort (with 2^k buckets) in my head. But I learned today that this isn't true!

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.

They also separately give algorithm for Fourier transform over complex number faster than O(n log n)

Wikipedia just told me there's a galactic algorithm for integer multiplication in O(n log n) based on FFT so I'm guessing those two proofs are related.

Multiplication is a lot like convolution, so the connection is natural.

multiplication is implemented w the fft

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)?

One way to think about it is that the classical algorithms are the ones that are fast for small numbers. Galactic algorithms often work for small inputs, it's just that to be faster you need big inputs. A common case of this is a requirement that log(n)<<klog(log(n)). If k=100 then this algorithm will take huge sizes to win

Can anyone ELI5 to make it make sense?

It seems n would have to be unimaginably large for this to make any difference. What changes about multiplication / FFT at large enough size ?

I guess nobody expected that it did before this result.

even though the constant is tiny, this breaks the long held assumption that nlogn is the minimal possible bound, so further research seemed unfruitful. this discovery will now trigger more research in this area, and probably more optimal algorithms will be discovered.

Like matrix multiplication, the common assumption was that it cannot be improved past n^3. Then Strassen broke the barrier (with a more significant constant) which caused intensive research - and now we are around n^2.3..2.4.

Reply on news.ycombinator.com