Name
Abstract | ||
|---|---|---|
We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information cost. In our examples the underlying distributions do not have full support. One interpretation of a distributions of non full support is as a promise given to the players (the players have a guarantee on their inputs). This brings up the issue of promise versus non-promise problems in this context. |
Year | Venue | Keywords |
|---|---|---|
2013 | Algorithmica | full support,zero error case,amortized communication complexity,underlying distribution,non full support,external information cost,direct sum,zero error communication complexity,average communication complexity,zero error average communication,non-promise problem,communication complexity,amortized complexity,information theory,average case complexity |
DocType | Volume | Issue |
Journal | 76 | 3 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gillat Kol | 1 | 19 | 3.44 |
| Shay Moran | 2 | 63 | 27.30 |
| Amir Shpilka | 3 | 1095 | 64.27 |
| Amir Yehudayoff | 4 | 530 | 43.83 |