An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
From MaRDI portal
Publication:2828217
DOI10.1145/2858785zbMath1347.68163arXiv1403.1307OpenAlexW2257409780MaRDI QIDQ2828217
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.1307
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform ⋮ Paraunitary matrices, entropy, algebraic condition number and Fourier computation
Cites Work
- Unnamed Item
- Unnamed Item
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Quantum Computation and Quantum Information
- Tighter Fourier Transform Lower Bounds
- On computing the Discrete Fourier Transform
- Optimality of the Fast Fourier transform
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
This page was built for publication: An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
