TY - GEN
T1 - Direct sum fails for zero error average communication
AU - Kol, Gillat
AU - Moran, Shay
AU - Shpilka, Amir
AU - Yehudayoff, Amir
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893210124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893210124&partnerID=8YFLogxK
U2 - 10.1145/2554797.2554844
DO - 10.1145/2554797.2554844
M3 - Conference contribution
AN - SCOPUS:84893210124
SN - 9781450322430
T3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
SP - 517
EP - 522
BT - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PB - Association for Computing Machinery
T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Y2 - 12 January 2014 through 14 January 2014
ER -