2016/04/09 by Nir Ailon, Gal Yehuda, Ailon, Nir +1
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Mathematical Analysis and Transform Methods #Matrix Theory and Algorithms #Random Matrices and Applications #cs.CC
paper · pdf · doi:10.48550/arxiv.1604.02557
openalex publication_date 2016/04/09 · arxiv created 2019/04/17 · arxiv updated 2019/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.