Trading Communication Rounds for Total Bandwidth

25 concepts19 papers2 proposals

Imagine Alice wants to convey a secret to Bob, and she knows Bob already holds some data correlated with her own. If Alice is restricted to sending a single, one-way message, she must over-communicate. To guarantee success, she has to account for every possible piece of information Bob might be missing, inflating the size of her message.

But what if they can talk back and forth? By breaking her message into smaller pieces and waiting for Bob's feedback, Alice can stop transmitting the moment Bob signals that he has enough pieces to solve the puzzle. This is the core intuition behind the round-communication tradeoff: increasing the number of interactive rounds can drastically reduce the total number of bits exchanged.

The Mechanism of Interactive Protocol Compression

How does talking back and forth actually save bits? The fundamental mechanism relies on using feedback to dynamically prune uncertainty.

In On Slepian-Wolf Theorem with Interaction, Alexander Kozachinskiy demonstrates how a one-way data transmission task can be compressed into a multi-round dialogue. Instead of Alice guessing Bob's side information upfront, interactive communication allows Bob to guide Alice. He can continuously signal what he understands, allowing Alice to terminate the protocol early the moment Bob uniquely identifies the source data.

To push this efficiency further, protocols can combine feedback with shared randomness. In Information Complexity Density and Simulation of Protocols, Shun Watanabe et al. show that parties can use public randomness to "guess" entire segments of a communication transcript. If the guess is correct, they bypass sending those bits entirely; if it is incorrect, a brief exchange of feedback corrects the trajectory. This interactive error-correction mechanism narrows the gap between actual communication cost and the underlying information complexity of the task.

Establishing Shared Secrets and Common Randomness

This tradeoff is highly visible when distributed parties attempt to generate shared cryptographic keys or common randomness from correlated observations.

Himanshu Tyagi in Common Information and Secret Key Capacity established a foundational link between interactive protocols and Wyner's common information. While simple binary data sources might not require interaction, more complex data distributions demand sophisticated back-and-forth exchanges to minimize the total communication bandwidth.

Once we accept that interaction helps, a critical question arises: How many rounds are actually needed? Does a third, fourth, or hundredth round continue to yield meaningful bandwidth savings?

One-Way Communication (1 Round):
Alice ------------------------------> Bob (Must send maximum bits to cover all uncertainty)

Interactive Communication (Multi-Round):
Alice ----(Small Chunk)-------------> Bob
Alice <---(Feedback/Correct?)-------- Bob
Alice ----(Next Small Chunk)--------> Bob (Protocol terminates early once resolved)

To map this scaling behavior, Mitali Bafna et al. in Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation analyzed how the total bit budget scales as the allowed round complexity increases. Similarly, Noah Golowich et al. in Round Complexity of Common Randomness Generation: The Amortized Setting investigated the exact thresholds where additional interaction rounds stop providing a significant reduction in bandwidth, helping define the fundamental limits of interactive agreement.

Bypassing Hardness in Distributed Estimation and Learning

In decentralized statistical inference, choosing between a one-shot architecture and a multi-round protocol can mean the difference between an exponential sample requirement and an efficient deployment.

Consider the problem of learning under privacy constraints. In Interaction is necessary for distributed learning with privacy or communication constraints, Vitaly Feldman et al. proved that single-round protocols face an exponential sample complexity barrier when performing high-dimensional learning under Local Differential Privacy (LDP). However, by introducing a small, fixed number of interaction rounds, the server and the users can adaptively adjust their queries based on prior responses, completely bypassing this exponential penalty.

A similar dynamic occurs in distributed hypothesis testing and estimation. While John Duchi et al. in Information-theoretic lower bounds for distributed statistical estimation with communication constraints mapped out how strict communication constraints degrade estimation accuracy, subsequent work has increasingly looked to interaction as a remedy. For instance, Lasse Vuursteen in Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime highlights how multi-round "blackboard" protocols—where nodes write to a shared, visible medium—can achieve superior statistical efficiency compared to rigid, independent messaging.

The Limits of Interaction

Despite its power, interaction is not a universal remedy. There are two major scenarios where adding communication rounds fails to reduce the total bit budget: statistical independence and structural sequentiality.

First, if a task lacks a structure that feedback can exploit, interaction provides zero advantage. In Communication Complexity of Estimating Correlations, Uri Hadar et al. demonstrated that for estimating the correlation between two distributed sources, a simple one-way message is just as effective as a highly complex, multi-round interactive protocol. The information required to pin down the correlation cannot be compressed via adaptive feedback.

Second, some problems are inherently sequential, meaning they require a minimum number of rounds regardless of how many bits you are willing to send in parallel. A classic example is the pointer chasing problem. In Pointer Chasing with Unlimited Interaction, Rotem Oshman et al. proved that even if parties are granted an unlimited number of communication rounds, they cannot beat the trivial strategy of following the path step-by-step.

When a problem's information structure is chained sequentially, interaction cannot compress the protocol; it merely acts as the unavoidable metronome of the computation.

Key Foundational Work

Common Information and Secret Key Capacity (2013) — contributed 1 concept elements to this direction.
Regret-based Incremental Partial Revelation Mechanisms (2006) — contributed 1 concept elements to this direction.
Secret key capacity for multipleaccess channel with public feedback (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_round_communication_tradeoff_2ee570e8,
  title = {round-communication tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/round-communication-tradeoff/rdr_2ee570e809be48bfa7fa698c136f614a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_round_communication_tradeoff_2ee570e8_v1,
  title = {round-communication tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/round-communication-tradeoff/rdr_2ee570e809be48bfa7fa698c136f614a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake