Constant-Loss Round-Preserving Direct Sums for Information Complexity
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.
Related
- KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
- Information Lower Bound for Regime Boundary Estimation — Optimal Precision Limit at the n² Scale and Universal Constant c=1/8 in the Fixed-Breakpoint Model
- Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs
- Design of Privacy-Preserving Estimators Under Prior Information Exposure
- The optimal information complexity of VC learning
BibTeX
@misc{wang2026constantloss,
title = {{Constant-Loss Round-Preserving Direct Sums for Information Complexity}},
author = {Haoran Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15377},
eprint = {2610.15377},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15377},
}
RIS
TY - UNPB
TI - Constant-Loss Round-Preserving Direct Sums for Information Complexity
AU - Haoran Wang
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15377
UR - https://arxiv.org/abs/2610.15377
AB - 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.
ER -