Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-150 | 23rd September 2016 11:57

Streaming Communication Protocols


Authors: Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez
Publication: 23rd September 2016 18:43
Downloads: 940


We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents are allowed to communicate with each other and also update their memory based on the input bit they read and the previous message they received.

We provide tight tradeoffs between the necessary resources, i.e. communication and memory, for some of the canonical problems from communication complexity by proving a strong general lower bound technique. Second, we analyze the Approximate Matching problem and show that the complexity of this problem (i.e. the achievable approximation ratio) in the one-way variant of our model is strictly different both from the streaming complexity and the one-way communication complexity thereof.

ISSN 1433-8092 | Imprint