TY - GEN

T1 - Interactive information complexity

AU - Braverman, Mark

PY - 2012

Y1 - 2012

N2 - The primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x,y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x,y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (non-amortized) communication complexity. This connection implies that a non-trivial exchange of information is required when solving problems that have non-trivial communication complexity. We explore the information complexity of two specific problems - Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving Equality with no errors, while solving Disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.

AB - The primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x,y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x,y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (non-amortized) communication complexity. This connection implies that a non-trivial exchange of information is required when solving problems that have non-trivial communication complexity. We explore the information complexity of two specific problems - Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving Equality with no errors, while solving Disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.

KW - communication complexity

KW - information complexity

KW - information theory

KW - interactive computation

KW - privacy

UR - http://www.scopus.com/inward/record.url?scp=84862628239&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862628239&partnerID=8YFLogxK

U2 - https://doi.org/10.1145/2213977.2214025

DO - https://doi.org/10.1145/2213977.2214025

M3 - Conference contribution

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 505

EP - 524

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12

Y2 - 19 May 2012 through 22 May 2012

ER -