Faster Fourier Transforms

The Fourier Transform and its fast algorithms continue to be fundamentally useful in many areas of math, science, and technology. In one interpretation, the Fourier Transform takes the evaluations of a polynomial p at special points and finds the values of p's coefficients. The celebrated FFT algorithm for the Fourier Transform runs in time O(n*log(n)) given n evaluations. So the FFT requires little more time than to read the input; the naive algorithm runs in time O(n^2).

And yet, we can do better. If k n denotes the number of coefficients of significant size, recent algorithms can produce an approximation to p in time close to k*log(n), roughly the size of the output, not the much larger input. In this talk, we present the FFT algorithm and a typical sparse sublinear algorithm.