Direct sum fails for zero error average communication
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff · 2014
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.