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 (39)

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

This page was built for publication: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform