{"id":"openai-math/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform","pdf":"https://github.com/openai/math/blob/main/preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026","tags":["algorithms","discrete-fourier-transform"],"score":0,"title":"An explicit power saving for the exact discrete Fourier transform","domain":"Theoretical computer science","family":"130","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a deterministic algorithm that computes the discrete Fourier transform at every length n in $`O(n(\\log n)^{1-10^{-13}})`$ operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":2,"published":"2026-09-25","reactions":{},"discussion":[{"url":"https://x.com/beenwrekt/status/2109652311538843934","date":"2026-10-12","kind":"x","added":"2026-10-24","author":"Ben Recht","handle":"beenwrekt"},{"url":"https://www.argmin.net/p/faster-fourier-transforms","date":"2026-10-14","kind":"web","site":"argmin.net","text":"The OpenAI algorithm for the FFT is less a breakthrough and more a malicious exploit.","added":"2026-10-24","title":"Faster Fourier Transforms","author":"Ben Recht"}],"formalized":true,"family_title":"Exact Fourier transforms below $`n\\log n`$"}