ECCC-Report TR14-113https://eccc.weizmann.ac.il/report/2014/113Comments and Revisions published for TR14-113en-usWed, 27 Aug 2014 00:17:56 +0300
Paper TR14-113
| Exponential Separation of Information and Communication for Boolean Functions |
Anat Ganor,
Gillat Kol,
Ran Raz
https://eccc.weizmann.ac.il/report/2014/113We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function 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 of boolean functions cannot hold, answering a long standing open problem.
Our techniques build on [GKR14], that proved a similar result for relations with very long outputs (double exponentially long in $k$). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions.
Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.Wed, 27 Aug 2014 00:17:56 +0300https://eccc.weizmann.ac.il/report/2014/113