Name
Abstract | ||
|---|---|---|
We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.27 | FOCS |
Keywords | DocType | Volume |
communication complexity,protocols,amortized communication complexity,communication protocol,distributional communication complexity,information complexity,amortized communication complexity,communication complexity,communication compression,direct sum,information complexity | Journal | 21 |
ISSN | Citations | PageRank |
0272-5428 | 13 | 0.63 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anat Ganor | 1 | 24 | 3.92 |
| Gillat Kol | 2 | 19 | 3.44 |
| Ran Raz | 3 | 2772 | 180.87 |