Communication-Space Tradeoffs for Unrestricted Protocols
- 1 June 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (3) , 652-661
- https://doi.org/10.1137/s0097539791196883
Abstract
. This paper introduces communicating branching programs, and develops a generaltechnique for demonstrating communication-space tradeoffs for pairs of communicating branchingprograms. This technique is then used to prove communication-space tradeoffs for any pair ofcommunicating branching programs that hashes according to a universal family of hash functions.Other tradeoffs follow from this result. As an example, any pair of communicating Boolean branchingprograms that computes...Keywords
This publication has 12 references indexed in Scilit:
- On the distributional complexity of disjointnessPublished by Springer Nature ,2005
- A time-space tradeoff for Boolean matrix multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Trade-offs between communication and spaceJournal of Computer and System Sciences, 1992
- Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offsJournal of Computer and System Sciences, 1992
- Monotone circuits for matching require linear depthJournal of the ACM, 1992
- Time-space tradeoffs for algebraic problems on general sequential machinesJournal of Computer and System Sciences, 1991
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982
- A time-space tradeoff for sorting on non-oblivious machinesJournal of Computer and System Sciences, 1981
- New hash functions and their use in authentication and set equalityJournal of Computer and System Sciences, 1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979