Information bounds keep constant while preserving rounds in communication tasks
Constant-Loss Round-Preserving Direct Sums for Information Complexity
Computational ComplexityInformation Theory
Summary
When solving many separate communication problems at once, it’s important to know how much information is needed overall compared to just one problem. The authors found a way to keep the number of back-and-forth messages (rounds) the same without increasing the amount of information lost, even if the number of problems grows. They introduced methods that carefully measure variance and information, allowing for more efficient communication with constant losses. This work helps understand how to split complex tasks into simpler parts without extra communication overhead.
What this means in practice
- •For communication system designers: Optimize multi-instance communication protocols without increasing message rounds or information loss.
- •For data compression engineers: Develop compression schemes that maintain efficiency when encoding multiple independent data streams with round constraints.
A theory result. No direct application yet.
Authors
Haoran Wang
Abstract
Strong direct-sum theorems relate the information needed to solve many independent instances of a communication problem to the information needed for one instance. For Gap-Majority composition, an optimal information bound was previously known, but preserving the number of communication rounds incurred an additional logarithmic loss. We prove a round-preserving Gap-Majority lemma with constant additive information loss, independent of both the number of instances and the number of rounds. More generally, we establish a variance direct-sum theorem for additive square-integrable observables over product distributions. For protocols with a bounded number of terminal answer values, the extracted single-coordinate protocols preserve the round budget, and their average information cost is at most the original information cost divided by the number of coordinates, plus a term depending only on the answer alphabet and the allowed variance loss. The proof uses centered counterfactual conditional means and a global variance amortization argument. Rather than encoding absolute conditional means for every possible terminal answer, we encode the information not already determined by the common view. The total squared innovation is controlled by a telescoping variance potential, yielding an information loss independent of the number of coordinates. We also derive same-round mean-square estimation bounds for arbitrary terminal outputs.