Tighter Fourier Transform Lower Bounds

DOI10.1007/978-3-662-47672-7_2zbMath1435.68108arXiv1404.1741OpenAlexW822096598MaRDI QIDQ3448770

Nir Ailon

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.1741

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)

Related Items

Tighter Fourier Transform Lower Bounds, The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform, Paraunitary matrices, entropy, algebraic condition number and Fourier computation, An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model

Cites Work

• Unnamed Item
• Unnamed Item
• Even faster integer multiplication
• Fast dimension reduction using Rademacher series on dual BCH codes
• Fast and RIP-optimal transforms
• Fast Integer Multiplication Using Modular Arithmetic
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Tighter Fourier Transform Lower Bounds
• Sampling from large matrices
• Faster Integer Multiplication
• On computing the Discrete Fourier Transform
• Optimality of the Fast Fourier transform
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• An Algorithm for the Machine Calculation of Complex Fourier Series
• (Nearly) Sample-Optimal Sparse Fourier Transform
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform