Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-047 | 10th March 2017 13:52

An Interactive Information Odometer with Applications

Revision #1
Authors: Mark Braverman, Omri Weinstein
Accepted on: 10th March 2017 13:52
Keywords:

Abstract:

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If $I$ bits of information are required for solving a single copy of $f$ under $\mu$ with probability $2/3$, then any protocol attempting to solve $n$ independent copies of $f$ under $\mu^n$ using $o(n\cdot I)$ communication, will succeed with probability $2^{-\Omega(n)}$. This is the best one can hope for, as Braverman and [BR11] previously showed that $O(n\cdot I)$ communication suffice to succeed with probability $\sim (2/3)^n$.

We then show how the information odometer can be used to achieve information-theoretic secure communication between two untrusted parties:If the players' goal is to compute a function $f(x,y)$, and $f$ admits a protocol with information cost is $I$ and communication cost $C$, then our odometer can be used to produce a robust" protocol which: $(i)$ Assuming both players are honest, computes $f$ with high probability, and $(ii)$ Even if one party is malicious, then for any $k\in\N$, the probability that the honest player reveals more than $O(k\cdot (I+\log C))$ bits of information to the other player is at most $2^{-\Omega(k)}$.

Finally, we outline a potential approach which uses our odometer as a proxy for braking state of the art interactive compression results: Any progress on interactive compression in the regime where $I=O(\log C)$ will lead to new \emph{general} compression results in all regimes. In particular, any improvement on the dependence on $I$ in the $2^{O(I)}$ compression result of [Bra12] will lead to improved compression and new direct sum and product theorems in communication complexity.

Changes to previous version:

An adjustment of the global constant ($c_\tau$) in Theorem 1 was added, following a technical miscalculation in Lemma 19. These changes only affect the results in the paper by an absolute global constant.

Paper:

TR14-047 | 8th April 2014 23:51

An Interactive Information Odometer with Applications

TR14-047
Authors: Mark Braverman, Omri Weinstein
Publication: 9th April 2014 05:18
Keywords:

Abstract:

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If $I$ bits of information are required for solving a single copy of $f$ under $\mu$ with probability $2/3$, then any protocol attempting to solve $n$ independent copies of $f$ under $\mu^n$ using $o(n\cdot I)$ communication, will succeed with probability $2^{-\Omega(n)}$. This is the best one can hope for, as Braverman and [BR11] previously showed that $O(n\cdot I)$ communication suffice to succeed with probability $\sim (2/3)^n$.

We then show how the information odometer can be used to achieve information-theoretic secure communication between two untrusted parties:If the players' goal is to compute a function $f(x,y)$, and $f$ admits a protocol with information cost is $I$ and communication cost $C$, then our odometer can be used to produce a robust" protocol which: $(i)$ Assuming both players are honest, computes $f$ with high probability, and $(ii)$ Even if one party is malicious, then for any $k\in\N$, the probability that the honest player reveals more than $O(k\cdot (I+\log C))$ bits of information to the other player is at most $2^{-\Omega(k)}$.

Finally, we outline a potential approach which uses our odometer as a proxy for braking state of the art interactive compression results: Any progress on interactive compression in the regime where $I=O(\log C)$ will lead to new \emph{general} compression results in all regimes. In particular, any improvement on the dependence on $I$ in the $2^{O(I)}$ compression result of [Bra12] will lead to improved compression and new direct sum and product theorems in communication complexity.

ISSN 1433-8092 | Imprint