CaltechAUTHORS
  A Caltech Library Service

Fast generalized DFTs for all finite groups

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] 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:
URLURL TypeDescription
https://doi.org/10.1109/FOCS.2019.00052DOIArticle
https://arxiv.org/abs/1901.02536arXivDiscussion Paper
Additional Information:© 2019 IEEE. Supported by NSF grant CCF-1815607 and a Simons Foundation Investigator grant.
Funders:
Funding AgencyGrant Number
NSFCCF-1815607
Simons FoundationUNSPECIFIED
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