A look at the math that OpenAI claims computes faster Fourier transforms
OpenAI’s recent claim of a faster-than-FFT algorithm for discrete Fourier transforms has reignited long-standing tensions between theoretical computer science and practical computing. Commenters question the use of idealized models such as exact complex arithmetic and unit-cost operations, arguing these allow “galactic” asymptotic improvements that are impossible to realize on physical hardware. Others defend pure theory and big-O analysis as historically important and potentially future-relevant, while warning that AI-generated proofs may amplify existing weaknesses in how complexity results are specified and interpreted.
Nature of the claimed faster FFT / multiplication results
- Many see the OpenAI FFT and integer-multiplication results as using a very strong, arguably unrealistic model: exact complex arithmetic or unit-cost arithmetic on numbers whose magnitude grows superpolynomially in the input size.
- Critics argue the asymptotic speedup “comes from” hiding work inside operations treated as O(1) (e.g., huge-number multiplication), so the improvement may be more about the model than about computation itself.
- Others note variants in finite fields (used in cryptography) may fit realistic cost models better and thus be more meaningful.
Big-O, constants, and “galactic” algorithms
- Recurrent theme: big-O ignores constants, so “galactic” algorithms can beat n log n asymptotically but only for absurdly large n.
- Some say this makes such results practically useless or even “exploits” of the formalism; others counter that big-O and complexity classes remain very useful theoretical tools.
- Blum’s speedup theorem is invoked: time bounds can always be improved at the cost of space, so “breaking” an n log n barrier is not necessarily a deep physical limit.
Models of computation
- Debate over models: Turing machines vs register/RAM models vs Real RAM vs exact complex/rational arithmetic.
- Defenders: any model is an abstraction; we already idealize integer operations as constant time.
- Critics: some models (e.g., exact complex arithmetic with unbounded magnitude) are “more wrong” than others if the goal is to approximate real computers or physics.
Value and purpose of theoretical CS
- One camp: if theorists don’t care about practical performance, their work is a puzzle game of little external interest; galactic results and unrealistic models reinforce this perception.
- Opposing camp: theory often precedes applications; many historically “useless” ideas (modular arithmetic, number theory, relativity) became crucial later. You cannot reliably predict which math will matter.
- Some emphasize that TCS is essentially mathematics, not engineering; complaining it’s impractical misunderstands its goals.
AI-generated math and community dynamics
- Several commenters feel the critique is really about theoretical CS in general, with OpenAI used as a hook.
- Concerns that LLMs will mass-produce formally correct but model-exploiting or galactic results, burdening human reviewers and misaligning incentives.
- Others welcome the math itself and argue that unless concrete errors or misstatements are shown, dismissing work as “slop” or “slopository” is more cultural rant than technical critique.