Fast Generalized DFTs for All Finite Groups
Abstract
For any finite group G, we give an algebraic algorithm to compute the generalized discrete Fourier transform with respect to G, using O(|G|ω/2+ϵ) operations, for any ϵ>0. Here, ω is the exponent of matrix multiplication.
Copyright and License
© 2024 Society for Industrial and Applied Mathematics
Acknowledgement
We thank Jonah Blasiak, Tom Church, and Henry Cohn for useful discussions during an AIM SQuaRE meeting, and Chloe Hsu for her helpful comments on an earlier version of this paper. We thank the FOCS and SICOMP referees for their careful reading and detailed suggestions.
Funding
This work was supported by NSF grant CCF-1815607 and a Simons Foundation Investigator grant.
Additional Information
This paper appeared in Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science, 2019: 10.1109/FOCS.2019.00052
Files
| Name | Size | Download all |
|---|---|---|
|
md5:16d00a84909e59518798bd3872b026ac
|
678.0 kB | Preview Download |
Additional details
- National Science Foundation
- CCF-1815607
- Simons Foundation
- Accepted
-
2024-05-20Accepted
- Publication Status
- In Press