Trade-offs between communication and space

DOI10.1016/0022-0000(92)90028-HzbMath0769.68047OpenAlexW2037766680WikidataQ58063101 ScholiaQ58063101MaRDI QIDQ1201877

Martin Tompa, Prasoon Tiwari, Tak-Wah Lam

Publication date: 17 January 1993

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(92)90028-h

zbMATH Keywords

Boolean modelcommunication complexityarithmetic modellimited work space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• Communication complexity
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• A time-space tradeoff for sorting on non-oblivious machines
• Graph-theoretic properties in computational complexity
• On the optimal evaluation of a set of bilinear forms
• A general class of resource tradeoffs
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Time-Space trade-offs for some algebraic problems
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Lower bounds on communication complexity in distributed computer networks
• A Time-Space Tradeoff for Element Distinctness
• A Communication-Time Tradeoff
• Lower Bounds on Information Transfer in Distributed Computations
• Alternation
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A new approach to error-correcting codes

This page was built for publication: Trade-offs between communication and space