ECCC-Report TR14-049https://eccc.weizmann.ac.il/report/2014/049Comments and Revisions published for TR14-049en-usSun, 11 May 2014 02:07:25 +0300
Revision 1
| Exponential Separation of Information and Communication |
Anat Ganor,
Gillat Kol,
Ran Raz
https://eccc.weizmann.ac.il/report/2014/049#revision1We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman, our gap is the largest possible. By a result of Braverman and Rao, 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.Sun, 11 May 2014 02:07:25 +0300https://eccc.weizmann.ac.il/report/2014/049#revision1
Paper TR14-049
| Exponential Separation of Information and Communication |
Anat Ganor,
Gillat Kol,
Ran Raz
https://eccc.weizmann.ac.il/report/2014/049We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman, our gap is the largest possible. By a result of Braverman and Rao, 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.Fri, 11 Apr 2014 07:28:07 +0300https://eccc.weizmann.ac.il/report/2014/049