Published by the Department of Computer Science, The University of Chicago.

Abstract

Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem. All lower bounds so far have made strong restrictions on the computational model. One of the best known results, by Morgenstern from 1973, provides an $\Omega(n \log n)$ lower bound for the unnormalized FFT when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The determinant of the unnormalized Fourier transform is $n^{n/2}$, and thus by showing that it can grow by at most a constant factor after each step yields the result. This classic result, however, does not explain why the normalized Fourier transform, which has a unit determinant, should take $\Omega(n\log n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2\times 2$ gates, one obtains an $\Omega(n\log n)$ lower bound. The well known FFT works in this model. The main conclusion from this work is that a potential function that might eventually help proving the $\Omega(n\log n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.

• The article: PDF (152 KB)
• Source material: ZIP (68 KB)
• BibTeX entry for this article (298 bytes)

Submitted June 20, 2013, revised October 11, 2013; published October 18, 2013.

© 2013 Nir Ailon
Licensed under a Creative Commons Attribution License

Article 11

Article 13

Volume 2013

Published articles