Abstract
This paper investigates the role of interaction in Common Randomness Generation (CRG) within the amortized setting. While interaction is known to reduce communication costs in one-shot scenarios, its benefit in the amortized limit—where parties process an infinite stream of correlated samples—was previously less clear. We present new lower bounds showing that increasing the number of communication rounds can exponentially reduce the total bits exchanged. Specifically, for a constructed "pointer-chasing" source, we demonstrate a significant separation in communication efficiency between $r$ and $r+2$ rounds, proving that interaction remains a powerful resource even in the limit of infinite data.
Introduction
A fundamental question in information theory and communication complexity is whether talking back and forth more often helps two parties agree on a secret key more efficiently. This problem, known as Common Randomness Generation (CRG), involves two parties, Alice and Bob, who receive correlated but non-identical data observations ($X$ and $Y$). Their goal is to agree on a shared secret key $K$ by communicating over a public channel, aiming to maximize the length of $K$ while minimizing the number of bits sent.
In the amortized setting, Alice and Bob have access to an infinite stream of these correlated samples. The primary metric of interest is the "rate": the number of bits of communication required per bit of shared randomness generated. While interaction is a known advantage in "one-shot" problems, its utility in the amortized limit was debated. For simple sources like the Binary Symmetric Source (BSS), one round of communication is as effective as many. This research asks: are there sources where interaction provides a provable, significant advantage in the amortized setting?
Methods
The study builds upon recent breakthroughs in round-communication tradeoffs for non-amortized cases by extending them to the amortized regime. The authors employ several theoretical frameworks:
- Pointer-Chasing Sources: The authors define a synthetic family of source distributions, $\mu_{r,n}$, based on the "pointer-chasing" problem. Alice and Bob hold permutations, and the target secret is the result of following a chain of these permutations. This source is designed to be difficult for protocols with few rounds but efficient for those with enough rounds to "chase" the chain.
- Information Complexity: The analysis shifts from direct bit measurement to analyzing the information revealed about inputs. Internal and external information complexity are used to characterize the achievable rate region for CRG.
- Compression and Simulation: To bridge the gap between information-theoretic limits and actual communication, the authors utilize advanced compression results to "compress" protocols that reveal $I$ bits of information into those using approximately $I$ bits of communication.
- Indistinguishability Proofs: Lower bounds are established by showing that protocols with insufficient rounds cannot distinguish between the actual correlated source and a "fake" source with independent inputs.
Key Results
The analysis of the pointer-chasing source $\mu_{r,n}$ (where $n$ relates to input size) yields a dramatic separation in communication requirements:
- Upper Bound: With $r+2$ rounds, Alice and Bob can generate $n$ bits of common randomness using only $O(r \log n)$ bits of communication.
- Lower Bound: With only $r$ rounds, generating the same $n$ bits of randomness requires at least $\Omega(\sqrt{n})$ bits of communication (ignoring logarithmic factors).
This represents a jump from logarithmic to polynomial communication costs by losing just two rounds of interaction. The results confirm that for sufficiently complex correlations, "rounds" are a fundamental resource that can be traded for "bandwidth," even when processing infinite data. This work significantly narrows the previous gap in understanding, moving from a separation between $r/2$ and $r+2$ rounds to a much tighter $r$ vs. $r+2$ rounds.
Discussion and Future Work
While the separation is substantial, a gap remains between the $O(\log n)$ upper bound and the $\Omega(\sqrt{n})$ lower bound; a tight result would ideally reach $\Omega(n)$. Furthermore, the current findings focus on cases where the key length is a constant fraction of $n$. The problem remains open for sublinear key lengths.
Future research may address the "Common Random Bits per Interaction Bit" (CBIB) problem, which requires more granular techniques to analyze how information is utilized round-by-round. This work underscores the flexibility of CRG—where parties only need to agree on any high-entropy value—as a factor that makes proving lower bounds particularly challenging compared to fixed-function computation.
Summary updated