Source-linked AI summary
Information Equals Amortized Communication
Mark Braverman, Anup Rao
TL;DR
The paper asks how to simulate sending a message to a receiver with partial information using communication near the additional information revealed. It develops interactive sampling and compression protocols, then derives exact amortized equivalence with internal information cost and conditional direct-sum results. The main caveat is that the simulation’s interaction and round dependence constrain the result.
Problem
Communicating a message correlated with X to a receiver holding side information Y requires a single-message method near the lower bound I(M; X|Y), beyond existing multi-copy results.
Method
The paper uses an interactive sampling protocol based on informational divergence to compress one-round and multi-round communication protocols.
Results
The internal information cost of computing f under a fixed distribution equals the amortized communication complexity of computing many independent copies, while direct-sum bounds follow conditionally from pointer-jumping complexity.
Takeaways & Limitations
Efficient protocol compression is equivalent to strong direct-sum theorems for communication complexity within the paper’s stated scope.
Takeaways & Limitations
The simulation is interactive, and its round dependence on informational divergence may be unavoidable because the divergence is not known to the players in advance.
Abstract
from arXiv · showhide
We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian-Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that M is a deterministic function of X. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. Our work implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible.
1 Introduction
The paper develops an interactive protocol for sending a message to a receiver with partial information, using communication close to the message’s additional information. It generalizes classical compression and addresses limitations of amortized, multi-copy approaches when the message is not determined by the sender’s input.
- Problem and result: The protocol simulates sending M to a receiver with side information Y using expected communication close to I(M; X|Y), up to a sublinear additive term.This quantity measures the new information M reveals about X to the receiver.
- Generalization: The result generalizes classical data compression by allowing partial receiver information and messages that need not be deterministic functions of X.Classical compression is recovered when Y is empty and M is a deterministic function of X.
- Generalization: When Y is empty and M is deterministic from X, the information learned equals H(M), and M can be encoded using expected length H(M) + 1.This connects the result to Shannon’s classical data-compression results.
- Prior work: Information-theoretic work commonly studies n independent copies, where Slepian-Wolf achieves roughly I(M; X|Y) average communication when M is determined by X.The multi-copy setting does not immediately yield a method for communicating a single message.
- Prior work: Prior single-message work did not handle the case where the receiver has partial information about the sender’s message.This is the gap addressed by the paper’s protocol.
2 Consequences in Communication Complexity
The paper connects internal information cost, protocol compression, and amortized communication complexity, establishing equality for repeated computation and conditional results for strong direct sums.
- Information measures: The amortized communication complexity is the limiting average communication per copy when computing independent instances of a function.It is defined using protocols computing n independent input pairs with bounded error in each coordinate.
- Information measures: Internal information cost measures the new information each party learns about the other’s input during a protocol.It is defined as I(X; π(X,Y)|Y) + I(Y; π(X,Y)|X).
- Protocol compression: The main technical result compresses one-round protocols according to internal information cost by privately known-distribution sampling.Theorem 2.1 has one player sample from P while the other, knowing Q, outputs the same element with probability exceeding 1−ε.
- Protocol compression: For a k-round protocol with internal information cost I, both parties can reconstruct the exact transcript using expected communication I + O(√(kI) + k) + 2k log(1/ε) on a high-probability event.The event has probability greater than 1−kε, and both outputs are distributed exactly according to the original transcript.
- Consequences: Internal information cost equals amortized communication complexity for computing many independent copies under a fixed input distribution.This compression scheme clarifies the relationship among the paper’s complexity measures.
- Consequences: Efficient Correlated Pointer Jumping would yield a near-optimal strong direct sum theorem, while sufficiently high CPJ complexity would violate direct sum.If R(CPJ(C,C/n)) = ˜O(C/n), then R(f^n) = ˜Ω(n·R(f)); a lower bound Ω((C log^a C)/n) yields the stated violation.
- Consequences: For bounded-round protocols, computing n copies requires at least Ω(n(C − r log(1/ε) − O(C·r))) communication.Here C is the best single-copy protocol’s communication complexity under distribution µ.
- Protocol compression: The sampling method differs from correlated sampling because the relevant distributions can be far apart and require communication rather than being sampled without communication.The protocol does not require prior knowledge or assumptions about the divergence D(P||Q).
3 Preliminaries
This section defines communication protocols, their transcripts and complexity measures, and internal information cost. It then relates information cost to communication and to computing many independent copies.
- Protocol model: A public-coin protocol is a distribution over private-coin protocols, and its communication complexity is the maximum bits transmitted in any run.Deterministic protocols are the special case where node-labeling distributions have singleton support.
- Protocol model: A protocol transcript consists of the public randomness together with all exchanged messages, including any specified message prefix.The notation π(x,y) denotes the transcript on inputs x,y.
- Information measures: Internal information cost is the sum I(π(X,Y);X|Y)+I(π(X,Y);Y|X), measuring information revealed to the two parties.Public randomness is handled by conditioning and averaging over the random choice.
- Information measures: Internal information cost is at most protocol communication: ICiµ(π) ≤ CC(π).Each transmitted bit reveals information to at most one party, yielding the bound.
- Amortized computation: For n independent copies, distributional complexity measures the communication needed to compute f in every coordinate with failure probability at most ρ per input.The strengthened theorem converts an n-copy protocol π into a single-copy protocol τ with the same communication and error bound.
- Amortized computation: The constructed single-copy protocol satisfies ICiµ(τ) ≤ ICiµ^n(π)/n ≤ CC(π)/n.The protocol publicly samples a coordinate, samples compatible auxiliary inputs, runs π, and outputs that coordinate’s result.
4 Proof of Theorem 2.1
The protocol uses shared randomness, indexed sampling, and progressively longer hash messages to make both players select the same sample from distributions P and Q. It achieves high agreement while communicating near the log-likelihood ratio, without prior knowledge of the divergence.
- Player A samples an element according to P, while Player B outputs a matching element with probability greater than 1 − ε.
- The communication is bounded by a term involving log P(a)/Q(a), log 1/ε, log log 1/ε, and additive constants, and requires no prior knowledge of D(P||Q).
- The protocol represents samples as points under P and Q, uses public random elements and pairwise-independent hashes, and progressively enlarges the candidate region.
- Player A sends an index for a block of sampled elements, then transmits additional hash values until Player B finds a consistent candidate or reports failure.
- The correct sample survives iteration t when 2^t^2 reaches the likelihood ratio P(x_i)/Q(x_i), while incorrect candidates survive with probability at most ε/2^(t+1).
- The expected number of rounds is Θ(D(P||Q)), although increasing expected communication by a constant factor reduces it to O(log D(P||Q)).
5 Correlated Pointer Jumping
Correlated pointer jumping encodes protocol executions as trees whose players hold different child distributions. The sampling protocol follows the correct path with high probability and communication controlled by its divergence cost.
- A correlated pointer jumping instance is a rooted tree whose non-leaf nodes belong to one player and whose leaves carry output labels.
- Each node has player-specific child distributions, and the goal is to sample a leaf according to the distribution induced by those successive choices.
- The divergence cost of a path sums node divergences, while instance divergence is its expected cost under the correct path distribution.
- Theorem 5.1 samples a correct path using a k-round protocol that succeeds on an event of probability greater than 1 − kε.
- Conditioned on success, both parties output the same correctly distributed path, with communication bounded by D(T) + 2k log(1/ε) + 5√(kD(T)) + 9k.
- For a protocol π, fixing inputs and public randomness yields a correlated pointer jumping instance whose expected divergence equals the protocol’s internal information cost.
6 Applications
The paper applies its sampling theorem to protocol compression, amortized communication, and direct sums. It establishes equality between internal information cost and amortized communication, and characterizes strong direct sums through correlated pointer jumping.
- Protocol compression: The compression proof applies the sampling procedure to correlated pointer jumping, giving expected communication near internal information cost with round-dependent overhead.
- Information and amortization: The paper proves an exact equality between amortized communication complexity and internal information cost.
- Information and amortization: Amortized communication is defined from computing n independent copies with error ρ in each coordinate, divided by n, when the limit exists.
- Protocol compression: For sufficiently large n, the compressed protocol computes n copies with per-copy communication at most ICiµ(π) + δ/2 while maintaining error at most ρ.
- Direct sums: The promise problem CPJ(C, I) is complete for direct sum: near-optimal protocols imply direct sums for all promise problems, while failure of compression yields a counterexample.
- Direct sums: If CPJ(C, C/n) requires substantially more than C/n communication, it itself provides a counterexample to direct sum; conversely, efficient CPJ protocols yield strong direct-sum bounds.