Name
Abstract | ||
|---|---|---|
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.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/3276748 | ICALP |
Keywords | DocType | Volume |
Communication complexity, approximate matching, networks, streaming algorithms | Journal | 10 |
Issue | ISSN | Citations |
4 | 1942-3454 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lucas Boczkowski | 1 | 0 | 0.34 |
| Iordanis Kerenidis | 2 | 291 | 30.58 |
| Frédéric Magniez | 3 | 570 | 44.33 |