Trade-offs between communication and space

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

Tak-Wah Lam, Prasoon Tiwari, Martin Tompa

Publication date: 17 January 1993

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

zbMATH Keywords

Boolean model; communication complexity; arithmetic model; limited work space

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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