A look at the math that OpenAI claims computes faster Fourier transforms
OpenAI's claimed faster FFT is asymptotically faster only under exact complex arithmetic that implies exponential memory, so practical speedup is doubtful; the debate is whether such galactic theory is useful or exploita
Ben Recht argues OpenAI's claimed faster Fourier transform is not a practical breakthrough but a galactic algorithm: it is asymptotically faster only under big-O while hiding constants so large that n must be impossibly huge. The construction assumes exact complex arithmetic with superpolynomially growing magnitudes, implying exponential memory and constant-time arbitrary-precision multiplication, unlike real computers.
He ties this to Morgenstern's 1973 lower bound and Ailon's numerical-instability result, and criticizes a theory culture that rewards formal asymptotic results detached from computation.
Key takeaways
- OpenAI's main.pdf claims an FFT with a smaller log(n) factor than Cooley-Tukey, but Recht says the asymptotic gain is swamped by hidden constants estimated around 10^100 at n=10^12.
- The algorithm requires exact complex arithmetic and multiplies numbers whose magnitudes grow superpolynomially with n; storing them as bits would need memory exponential in input length.
- Morgenstern (1973) proved no FFT faster than ½ n log n under bounded coefficient magnitude; Ailon later showed faster transforms require severe numerical instability.
- Recht also cites an OpenAI matrix-multiplication result in O(n^2.25) whose hidden constant cannot be estimated, calling it another galactic algorithm.
- He argues such papers might be accepted at STOC/FOCS but reflect a theoretical CS culture that discourages running algorithms on actual computers.
What people think
Analysis details
17 comments analyzed. Analyzed .
The sample selects active discussion branches and includes available parent comments. It may omit parts of the full thread. The analysis included 17 of 20 usable stored comments because of the input limit. Selected themes do not measure community opinion or how common a view is.
Practical relevance and venue separation in algorithms theory
Commenters dispute whether theoretical algorithms must be practically implementable. One defends theory venues such as STOC/FOCS/SODA as mathematics, saying applied work belongs at ESA, ALENEX, VLDB/SIGMOD and that large constants are acceptable. Others question why to care about theory without practical performance, call results with no possible practical relevance useless, and argue the author's critique would also dismiss median-of-medians and Harvey–van der Hoeven multiplication.
Exact arithmetic model and exponential memory requirements
Commenters question the computational model behind recent complexity results, asking whether exact complex/real arithmetic is a standard premise. They note the algorithm assumes multiplying complex numbers with superpolynomially growing magnitudes in one operation; storing them as bits would require exponential memory, and such an oracle could encode impossible computations. Another notes Turing machines are not the usual model for complexity comparisons.
Replacing or supplementing big-O notation
One thread proposes replacing big-O because it permits galactic algorithms, and convincing theoreticians to use a less exploitable notation. Replies defend big-O's utility for defining complexity classes and analyzing algorithms, say replacements already exist, and cite Levin's Universal Search as an optimal-in-big-O but galactic algorithm that theorists do not treat as a final solution. Another reply says alternative notations might classify complexity classes without the same problem.
Long-term practical payoff of pure theory and mathematics
Commenters argue theoretical work can later yield practical breakthroughs, citing Fermat's modular arithmetic leading to cryptography and mathematics waiting centuries for computers, cryptography, and error-correcting codes. A counterpoint says they do not care until there is a real practical result and that math can be developed in service of a problem rather than purely abstractly.
Funding expectations for theoretical computer science
One commenter suggests many funders of theoretical CS likely assume the work has a realistic computational model behind it, distinguishing it from pure mathematics.
Ongoing efforts to improve integer multiplication bounds
Commenters point to a GitHub repository tracking improved bounds for integer multiplication, reporting a larger kappa value, and express surprise at the repository's high activity and many pull requests.