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

DOI10.1016/0022-0000(80)90056-2MaRDI QIDQ1140426zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3532851 (Why is no real title available?)
• scientific article; zbMATH DE number 3565023 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3363674 (Why is no real title available?)
• A Time-Space Trade-Off
• A note on time-space tradeoffs for computing continuous functions
• Graph-theoretic properties in computational complexity
• Parallel concepts in graph theory
• Shifting Graphs and Their Applications
• Space-time trade-offs on the FFT algorithm

Cited in

(21)

• Eigenvalues and expanders
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Two time-space tradeoffs for element distinctness
• Time-space efficient algorithms for computing convolutions and related problems
• Highly symmetric expanders
• Diameters and Eigenvalues
• Upper bounds for time-space trade-offs in sorting and selection
• Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
• Approximation of seismic velocities from the spectrum of weighted graphs
• The computational complexity of universal hashing
• Size bounds for superconcentrators
• Extreme time-space tradeoffs for graphs with small space requirements
• The performance of multilective VLSI algorithms
• Time-space tradeoffs for algebraic problems on general sequential machines
• On Reducing the Space Requirements of a Straight-Line Algorithm
• Size-space tradeoffs for oblivious computations
• Trade-offs between communication and space
• Extending the Hong-Kung model to memory hierarchies
• On time versus space III
• Time-space tradeoffs in algebraic complexity theory
• Superconcentrators of depth 2

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

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