Information Equals Amortized Communication

Mark Braverman, Anup RaoIEEE Trans. Information Theory 2014 · DOI

TL;DR

This paper establishes a fundamental equivalence between the "internal information cost" of a communication protocol and its "amortized communication complexity." This means the minimum information a protocol must reveal about its inputs is precisely what's needed to communicate many copies of a function efficiently. They also introduce a new problem, "Correlated Pointer Jumping," which is shown to be crucial for proving strong direct sum theorems in communication complexity.

What Problem Does This Paper Address?

Imagine two parties, A and B, who want to compute a function together. They can communicate by sending messages, but they want to minimize the total number of bits sent. A natural lower bound on this communication is the amount of "new information" the message reveals about the inputs. This is related to the concept of mutual information in information theory.

Classical results like the Slepian-Wolf theorem show how to achieve near-optimal communication for transmitting many copies of correlated data, but these results often rely on the data being deterministic functions of each other or on averaging over many copies. The challenge this paper tackles is understanding the communication cost for a single message or function computation, especially when one party has some prior information about the message.

More broadly, the paper delves into the relationship between different measures of communication complexity, particularly the "amortized communication complexity" (how efficiently many copies of a function can be computed) and "internal information cost" (the information revealed by a protocol). A key question is whether these two measures are fundamentally linked.

Methods

The paper introduces a novel interactive protocol for efficiently sampling from a distribution P, where one party knows P and the other knows a related distribution Q. This protocol's communication cost is bounded by the informational divergence $D(P||Q)$, a measure of how much two probability distributions differ. This is a significant technical contribution.

This sampling protocol is then used as a building block to prove the main results:

  1. Information Equals Amortized Communication: They show that the internal information cost of computing a function $f$ is exactly equal to the amortized communication complexity of computing many copies of $f$. This is achieved by showing how to compress protocols based on their internal information cost.
  2. Correlated Pointer Jumping (CPJ): A new communication problem is defined, CPJ, which is a generalization of pointer jumping on trees. This problem is designed to be "hard to compress."
  3. CPJ and Direct Sum Theorems: The paper demonstrates that the existence of near-optimal protocols for CPJ is equivalent to the existence of strong direct sum theorems for randomized communication complexity. This means that if CPJ can be solved efficiently, then computing $n$ copies of any function is roughly $n$ times harder than computing one copy (the direct sum property). Conversely, if direct sum fails, CPJ serves as a counterexample.

Datasets

Not discussed in the paper. The paper deals with theoretical communication complexity and does not rely on specific datasets.

Key Insights and Ideas

  • Information is the Bottleneck: The core insight is that the minimum information a protocol must reveal about its inputs is the fundamental limit on how efficiently many copies of a function can be computed. This collapses a previously fuzzy relationship into a precise equality.
  • Divergence as a Communication Cost: The novel sampling protocol shows that the informational divergence between two distributions can directly bound the communication needed to sample from one when the other is known. This provides a powerful tool for analyzing communication protocols.
  • CPJ as a "Hard-to-Compress" Problem: The Correlated Pointer Jumping problem is ingeniously constructed to be resistant to compression. Its difficulty directly reflects the difficulty of achieving strong direct sum theorems.
  • Equivalence of Complexity Measures: The paper establishes a deep connection between information-theoretic measures (internal information cost) and computational complexity measures (amortized communication complexity), and also links these to the fundamental question of direct sum theorems.

Key Results

  • Theorem 2.3: For any function $f$, distribution $\mu$, and error $p$, the internal information cost $IC'_\mu(f, p)$ is exactly equal to the amortized communication complexity of computing $n$ copies of $f$ as $n \to \infty$.
  • Theorem 2.1: A protocol is presented that allows two parties to sample from a distribution $P$ (known to one party) using communication bounded by the informational divergence $D(P||Q)$ (where $Q$ is known to the other party), plus logarithmic terms.
  • Theorem 5.1: The CPJ problem can be solved with communication bounded by the divergence cost of the instance, plus logarithmic terms.
  • Theorem 6.5 & 6.6: These theorems establish the completeness of CPJ for direct sum theorems. They show that if CPJ can be solved efficiently, then direct sum holds for all promise problems, and vice-versa.

Limitations and Future Work

  • Interactive Nature: The sampling protocol and the resulting compression are interactive. While this is necessary for certain cases (especially when distributions are far apart), future work might explore non-interactive alternatives where possible.
  • Sublinear Additive Terms: The paper mentions that the simulation is "close to optimal" with a "sublinear additive term." While this is excellent, understanding the exact nature and necessity of these additive terms in various scenarios could be a direction for future research.
  • Worst-Case vs. Average-Case: The paper primarily focuses on average-case and randomized communication complexity. Extending these results or understanding the interplay with worst-case complexity remains an area of interest.
  • CPJ and Compression: The paper highlights that CPJ is the "hardest problem to compress." Further investigation into the precise compression bounds for CPJ and its implications for other communication complexity problems would be valuable.

Summary updated

BibTeX
@article{braverman2014information,
  author = {Mark Braverman and Anup Rao},
  title = {{Information Equals Amortized Communication}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  doi = {10.1109/tit.2014.2347282},
}
Figure