Published November 2019
| Submitted
Book Section - Chapter
Open
Fast generalized DFTs for all finite groups
- Creators
- Umans, Christopher
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.
Additional Information
© 2019 IEEE. Supported by NSF grant CCF-1815607 and a Simons Foundation Investigator grant.Attached Files
Submitted - 1901.02536.pdf
Files
1901.02536.pdf
Files
(250.7 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:ba9cd9b0dc0efb0196a96c7f9441e670
|
250.7 kB | Preview Download |
Additional details
- Eprint ID
- 99867
- DOI
- 10.1109/FOCS.2019.00052
- Resolver ID
- CaltechAUTHORS:20191115-133902016
- CCF-1815607
- NSF
- Simons Foundation
- Created
-
2019-11-15Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field