Is 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.
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.
Wouldn't it take an infinite lookup table to do this satisfying any two integers and still get an order-complexity speedup? The integers can be any size. You can't specify an arbitrarily variable sized lookup table in the normal formulation of these problems without computing the lookup table as part of the computation.
Never infinite if you have bounds on integer size. For n bits of input it's always possible to have a 2^n space complexity lookup table that's O(1) speed since 2^n covers all possibilities of n bits.
You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.
I think the thing non-mathematicians and non-CS people who only know complexity theory vaguely need to remember is that complexity theory has nothing to do with reality.
A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)
Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite. Thats the end state of Blums speedup theorem in either direction and it doesn’t limit to any bounds. I just stating a limited of bounds above for the sake of giving understanding. Complexity theory doesn’t care that 2^n space complexity doesn’t work when n is infinite anymore than it cares that nlogn also doesn’t work when n is infinite. It’s not the point.
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.
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.
But your right in that we don’t have a huge LUT as it’s not worth it.
Small one in the ALU though, for partial products to add can be worth the additional wire length.
You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.
A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)
The whole point of complexity theory is that there are no bounds on input size.
https://nitter.kareem.one/RohanArun/status/21093360158149592...
(Replace top-level with healthy instances or x.com as needed)