Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-123 | 15th September 2011 02:37

Interactive information complexity


Authors: Mark Braverman
Publication: 15th September 2011 02:40
Downloads: 9754


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. We explore the information complexity of two specific problems -- Equality and Disjointness. We conclude with a list of open problems and research directions.

ISSN 1433-8092 | Imprint