alt Hacker News> the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n.
Err... doesn't that completely invalidate the big-O analysis!?
I suspected that these Open AI "proofs" of sub-nlogn times were cheating somehow, by sweeping something under a rug. This seems to be it!
Replies
LPisGood • today at 4:00 AM
You can be linear in the bit length of the input number, but exponential in the magnitude.
This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”
I can't speak for the FFT claim, but least the sub-O(n log n) multiplication claim is for the multitape Turing machine model with a fixed number of tapes, which if anything is more restrictive than actual random-access memory. Of course, it's still galactic just like the O(n log n) algorithm, but it definitely seems like there's something there.