文章基本信息

标题：Streaming Communication Protocols
本地全文：下载
作者：Lucas Boczkowski ; Iordanis Kerenidis ; Fr{\'e}d{\'e}ric Magniez 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：130:1-130:14
DOI：10.4230/LIPIcs.ICALP.2017.130
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. Input arrives as a stream, spread between several agents across a network. Each agent has a bounded memory, which can be updated upon receiving a new bit, or a message from another agent. We provide tight tradeoffs between the necessary resources, i.e. communication between agents 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.
关键词：Networks; Communication Complexity; Streaming Algorithms