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