|
Fourier transforms below $n\log n$
at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages
LOADING...
0%
thinking... about 3 hours remaining
GAME #130
Fourier transforms below $n\log n$
The Fast Fourier Transform, but even faster. Don't blink!
PLAY
LEAN
VERIFIED
If this game doesn't work on your computer, go here for help. (Lean version available!)expertly designed by an internal OpenAI model
| >>> How to Play <<< |
| Exact Fourier transforms below $n\log n$. Gives a deterministic length-n discrete Fourier transform algorithm using $O(n(\log n)^{1-\delta})$ operations for every n, with explicit $\delta=10^{-13}$. The model uses exact complex arithmetic, unrestricted coefficients and a supplied root of unity, and counts scalar preparation and logarithmic-word indexing. |
| >>> Level Select <<< |
|
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.
| |
We construct exact nonuniform Fourier circuits of size $o(n\log n)$ along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. This refutes the $\Omega(n\log n)$ lower bound in the unrestricted complex linear-circuit model. The construction uses a finite tensor saving: a tensor power of some invertible nonmonomial complex matrix can be computed with fewer matrix calls than the standard tensor-axis algorithm on the same coordinates, when invertible monomial maps are allowed freely between calls.
|
|