Round Complexity of Common Randomness Generation: The Amortized Setting

Noah Golowich, Madhu Sudan

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?

Schematic of the amortized Common Randomness Generation (CRG) setup. Alice and Bob receive correlated sequences $X_i$ and $Y_i$ and interact to agree on keys $K_A$ and $K_B$.

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

We study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples $X_i$ and $Y_i$, respectively, drawn jointly from a source distribution $μ$. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem: they gave a family of sources $μ_{r,n}$ parameterized by $r,n\in\mathbb{N}$, such that with $r+2$ rounds of communication one can generate $n$ bits of common randomness with this source with $O(r\log n)$ communication, whereas with roughly $r/2$ rounds the communication complexity is $Ω(n/{\rm poly}\log n)$. Note that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair $r,n \in \mathbb{N}$ the (amortized) communication complexity to generate $Ω(n)$ bits of common randomness from the source $μ_{r,n}$ using $r+2$ rounds of communication is $O(r\log n)$ whereas the amortized communication required to generate the same amount of randomness from $r$ rounds is $Ω(\sqrt n)$.
BibTeX
@inproceedings{golowich2019round,
  author = {Noah Golowich and Madhu Sudan},
  title = {{Round Complexity of Common Randomness Generation: The Amortized Setting}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=6knQVf70gS},
}
Figure