Is $O (N \log N)$ FFT speed the fastest we can ever attain? I am wondering about whether or not there is a theoretical limit as to the speed at which we can compute a DFT. We all know that the FFT executes in $O (N \log N)$ time. However, is this a lower bound of some sort? 

Might there be yet faster algorithms that have yet to be discovered which we do not currently know about that are faster, or is this a holy boundary that cannot be crossed?

Edit: Apparently this is a known unsolved problem in CS, (thanks to @John). 

So, what are the details of the problem? Where would one start to try to make improvements?
While the general problem remains an open problem in theoretical computer science, there are (randomized) algorithms known as sparse fast fourier transforms which can approximate DFTs to a certain approximation factor when there are only a few DFT coefficients you are concerned with. 

You can find some details in these papers and related papers (downloadable here):


Hassanieh, Haitham, et al. "Nearly optimal sparse Fourier transform." Proceedings of the 44th symposium on Theory of Computing. ACM, 2012.
Hassanieh, Haitham, et al. "Simple and practical algorithm for sparse Fourier transform." Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2012.