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|
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω/2+ε</sup>
) operations, for any ε > 0. Here, ω is the exponent of matrix multiplication. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/FOCS.2019.00052 | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | Field | DocType |
Discrete Fourier Transform,finite group,algorithm | Discrete mathematics,Combinatorics,Exponent,Omega,Discrete Fourier transform,Finite group,Matrix multiplication,Mathematics | Journal |
Volume | ISSN | ISBN |
abs/1901.02536 | 1523-8288 | 978-1-7281-4953-0 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christopher Umans | 1 | 879 | 55.36 |