Space-time trade-offs on the FFT algorithm

DOI10.1109/TIT.1978.1055938MaRDI QIDQ4158442zbMATH OpenOpenAlexFDO

Authors Sowmitri Swamy, John Savage

Publication date 1978

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.1978.1055938

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Numerical methods for trigonometric approximation and interpolation (65T40)

Cited in

(18)

• Size-space tradeoffs for oblivious computations
• Lower bounds in algebraic computational complexity
• The performance of multilective VLSI algorithms
• Time-space efficient algorithms for computing convolutions and related problems
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• A space bound for one-tape multidimensional Turing machines
• A time-space tradeoff for sorting on non-oblivious machines
• Extreme time-space tradeoffs for graphs with small space requirements
• A general class of resource tradeoffs
• Time-space tradeoffs in algebraic complexity theory
• Nullstellensatz size-degree trade-offs from reversible pebbling
• On Reducing the Space Requirements of a Straight-Line Algorithm
• Space-time tradeoffs for linear recursion
• Cumulative space in black-white pebbling and resolution
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Depth-robust graphs and their cumulative memory complexity
• On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives
• Quantum time-space tradeoffs for matrix problems

This page was built for publication: Space-time trade-offs on the FFT algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4158442)