alt Hacker NewsIs there any good writeup yet of intuitively where the speedup comes from? E.g. with fast fourier transform you can see that there's a lot of symmetry & recomputation in the Vandermonde matrix, so that's where the speed up comes from.
Replies
Ben Recht has a nice blog post about how these results are basically reward hacking the TCS formalization by assuming atomic operations for exact complex arithmetic, instead of costs scaling with the size/precision of the number: https://www.argmin.net/p/faster-fourier-transforms
number multiplication is basically convolution and closely tied with FFTs, so I wouldn't personally be surprised even if a lot of the "FFT's work" could somehow be stuffed into exact arithmetic operations, and the remaining costs just track the packing and unpacking from that representation. It's just an exploit of the book-keeping.
That's ignoring the other complaints about this being a galactic algorithm.
The site is taking forever to load but complexity theory doesn't really have the hard walls at things like O(nlogn) that people seem to think.
You can always always tradeoff time vs space. It's actually a fundamental part of complexity theory called Blums speedup theorem by the guy who invented complexity theory no less.
As an example you give me an nlogn solution and i take a portion of the inner loop, put it in a lookup table (who cares if the lookup table is 2^n in size, that's not what we're measuring here since we're specifically measuring time not space) and suddenly i have something better than nlogn since that lookup table is O(1).
That's not to say there's some merit to all of this. It's just that people shouldn't be as astonished by these results as they are. It's complexity theory. There's literally no such thing as a hard wall where something is nlogn in time and can't get lower. It can always get lower. But you need both the time and space complexities together to reason about this.