Lower Bounds for Fourier Transform Computation
.Finding the complexity of the n-dimensional Fourier transform computation has been an evasive problem for over 50+ years. The FFT (Fast Fourier Transform) of Cooley and Tukey (1965) gives an upper bound of O(n log n), but nothing better than Omega(n) has been known in a reasonable model of computation. In the talk I will show that speedup of Fourier computation implies loss of accuracy on a machine using words of fixed size (e.g. 32 or 64 bits). In order to recover the accuracy, one must work with words of size \omega(1), giving rise to an effective lower bound of Omega(n log log n).