  The complexity of computing the Fourier transform is a longstanding open
problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of
papers that, roughly speaking, a speedup of the Fourier transform computation
implies numerical ill-condition. The papers also quantify this tradeoff. The
main method for proving these results is via a potential function called
quasi-entropy, reminiscent of Shannon entropy. The quasi-entropy method opens
new doors to understanding the computational complexity of the important
Fourier transformation. However, it suffers from various obvious limitations.
This paper, motivated by one such limitation, partly overcomes it, while at the
same time sheds llight on new interesting, and problems on the intersection of
computational complexity and group theory. The paper also explains why this
research direction, if fruitful, has a chance of solving much bigger questions
about the complexity of the Fourier transform.
