Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform

DOI10.1145/321752.321761zbMath0258.65120OpenAlexW2027377011WikidataQ54087144 ScholiaQ54087144MaRDI QIDQ5674381

Jacques Morgenstern

Publication date: 1973

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321752.321761

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical methods for trigonometric approximation and interpolation (65T40)

Related Items

Lower bounds for off-line range searching, Binary determinantal complexity, A note on the use of determinant for proving lower bounds on the size of linear circuits, Tighter Fourier Transform Lower Bounds, On the computational complexity of the general discrete Fourier transform, A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle, Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness, Fast generalized Fourier transforms, Lower bounds for polynomial evaluation and interpolation problems, On the computation complexity of the systems of finite abelian group elements, Application of separability and independence notions for proving lower bounds of circuit complexity, The lower bounds on the additive complexity of bilinear problems in terms of some algebraic quantities, Additive complexity in directed computations, Size bounds for superconcentrators, Min-rank conjecture for log-depth circuits, The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform, Matrix rigidity, Invariant and geometric aspects of algebraic complexity theory. I, On the additive complexity of GCD and LCM matrices, Existence and efficient construction of fast Fourier transforms on supersolvable groups, On the arithmetic operational complexity for solving Vandermonde linear equations, Entropy of operators or why matrix multiplication is hard for depth-two circuits, Fast modular transforms, Time optimization of segmentation methods for computing the bounds of correlation functions, On Bellman's and Knuth's problems and their generalizations, Relation between two measures of the computation complexity for systems of monomials, Lower bounds for matrix factorization, Lower Bounds for Multiplication via Network Coding, A super-quadratic lower bound for depth four arithmetic circuits, An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model, Lower bounds for matrix factorization, Comparing the computational complexity of monomials and elements of finite abelian groups, Lower bounds in algebraic computational complexity, Cancellation-free circuits in unbounded and bounded depth, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms, Arithmetic complexity of certain linear transformations, The arithmetic computational complexity of linear transforms, A sparse fast Fourier algorithm for real non-negative vectors