Exponential Separation of Information and Communication for Boolean Functions

by Anat Ganor, Gillat Kol, and Ran Raz

Oded's comments

This is the improvement that was announced in an update comment on nr 149. Again, I think the abstract talks for itself, but this time I'd only stress that this refers to a decision problem (with a promise).

The original abstract

We 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.

see ECCC TR14-113.


Back to list of Oded's choices.