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?