Umans, Christopher (2019) Fast generalized DFTs for all finite groups. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 793-805. ISBN 978-1-7281-4952-3. https://resolver.caltech.edu/CaltechAUTHORS:20191115-133902016
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
See Usage Policy. 250kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191115-133902016
Abstract
For any finite group G, we give an arithmetic algorithm to compute generalized Discrete Fourier Transforms (DFTs) with respect to G, using O(|G|^(ω/2+ ϵ)) operations, for any ϵ > 0. Here, ω is the exponent of matrix multiplication.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| Additional Information: | © 2019 IEEE. Supported by NSF grant CCF-1815607 and a Simons Foundation Investigator grant. | |||||||||
| Funders: |
| |||||||||
| Subject Keywords: | Discrete Fourier Transform, finite group, algorithm | |||||||||
| DOI: | 10.1109/FOCS.2019.00052 | |||||||||
| Record Number: | CaltechAUTHORS:20191115-133902016 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20191115-133902016 | |||||||||
| Official Citation: | C. Umans, "Fast Generalized DFTs for all Finite Groups," 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, USA, 2019, pp. 793-805. doi: 10.1109/FOCS.2019.00052 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 99867 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 15 Nov 2019 22:42 | |||||||||
| Last Modified: | 16 Nov 2021 17:49 |
Repository Staff Only: item control page
