## Interactive Information Complexity

by Mark Braverman.

#### Oded's comments

This work initiates a (distribution independent) theory of
interactive information complexity.
It provides three closely related definitions that capture the
amount of information revealed to the parties by a randomized
communication protocol, where this means $I(exec;X|Y)+I(exec;X|Y)$.
The first two definitions differ by whether a protocol
is tailored for each input distribution
or is universal but analyzed per each input distribution.
The third definition is the (rather standard notion of)
amortized randomized communication complexity (CC).
One result states that these definitions are all
within a factor of two away from each other.
Another result states that information complexity (IC)
is additive wrt direct product. It is also shown that
in some cases IC is strictly smaller than randomized CC
(e.g., IC(EQ)=O(1) while CC(EQ) is linear, where both are error-less),
whereas in other cases it is essentially as high
(e.g., IC(DIST) is linear).

#### The original abstract

See TR11-123 of ECCC

Back to
list of Oded's choices.