| ▲ | xyzzyz 4 hours ago | |
They also separately give algorithm for Fourier transform over complex number faster than O(n log n) | ||
| ▲ | saalweachter 3 hours ago | parent [-] | |
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. | ||