Fall 2016

Uncertainty Seminar

Oct 6, 2016 4:00 pm – 5:30 pm 

Add to Calendar


Calvin Lab Rm 116

How Speeding Up an Algorithm Leads to Uncertainty: Fourier Transform Computation

The Fourier transform is one of the most important linear operators in engineering. Computing it for a given input vector x in n-space can be done in time Theta(n log n) using Cooley and Tukey's FFT (Fast Fourier Transform). A lower bound better than trivial \Omega(n) has been evasive. In this talk I will show the surprising connection between speeding up FFT and uncertainty: If you could (theoretically) speed up FFT without changing the word size on the machine, then you would create uncertainty in the data in the form of numerical overflow or underflow. Alas, increasing the machine word size costs more time per multiplication/addition operation. I will explain this principle and present two recent bounds (, together with the main conjecture and some related open problems. The talk requires standard linear algebra and very basic familiarity with Shannon entropy.