Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer

DOI10.1016/0022-0000(84)90029-1zbMath0577.68060OpenAlexW2009807436MaRDI QIDQ1065546

Yaacov Yesha

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90029-1

zbMATH Keywords

Lower boundsgeneral sequential modelrandom-access input

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (10)

On lower bounds for read-\(k\)-times branching programs ⋮ A note on the decoding complexity of error-correcting codes ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Trade-offs between communication and space ⋮ The computational complexity of universal hashing ⋮ Time-space tradeoffs for set operations ⋮ Trade-offs between communication throughput and parallel time ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

Cites Work

• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer