Time-space tradeoffs for computing functions, using connectivity properties of their circuits

DOI10.1016/0022-0000(80)90056-2zbMath0435.68034OpenAlexW2066947547MaRDI QIDQ1140426

Martin Tompa

Publication date: 1980

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(80)90056-2

zbMATH Keywords

convolutiondiscrete Fourier transformpolynomial multiplicationpebble gamegratesuper concentrator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (21)

Two time-space tradeoffs for element distinctness ⋮ Time-space efficient algorithms for computing convolutions and related problems ⋮ Upper bounds for time-space trade-offs in sorting and selection ⋮ Eigenvalues and expanders ⋮ On time versus space III ⋮ Extending the Hong-Kung model to memory hierarchies ⋮ Approximation of seismic velocities from the spectrum of weighted graphs ⋮ Superconcentrators of depth 2 ⋮ Size bounds for superconcentrators ⋮ Extreme time-space tradeoffs for graphs with small space requirements ⋮ 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 ⋮ On Reducing the Space Requirements of a Straight-Line Algorithm ⋮ Highly symmetric expanders ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Size-space tradeoffs for oblivious computations ⋮ The performance of multilective VLSI algorithms ⋮ Diameters and Eigenvalues

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph-theoretic properties in computational complexity
• A note on time-space tradeoffs for computing continuous functions
• Parallel concepts in graph theory
• Shifting Graphs and Their Applications
• Space-time trade-offs on the FFT algorithm
• A Time-Space Trade-Off

This page was built for publication: Time-space tradeoffs for computing functions, using connectivity properties of their circuits