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.