Comment by kingstnap
1 day ago
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.
2 replies →