Introduction
In classical information theory, Shannon's noisy-channel coding theorem establishes the maximum rate (Shannon capacity, $C_{Sh}$) at which data can be reliably transmitted over a noisy medium. This framework, however, typically assumes a "one-way" transmission where the entire message is known to the sender beforehand. In contrast, many real-world applications—ranging from distributed computing to remote gameplay—rely on interactive protocols where the next message depends on the previous exchange.
Interactive communication poses a unique challenge: a single undetected error can cause the internal states of the communicating parties to diverge, rendering all subsequent communication useless. This paper addresses the fundamental limits of such interactions by establishing a lower bound on the "essential interactive capacity" of Binary Memoryless Symmetric (BMS) channels.
Defining Essential Interactive Capacity
Previous research into interactive capacity often relied on simplifying assumptions, such as a fixed order of speakers or the availability of shared "public" randomness (random bits known to both parties but not the eavesdropper). The authors of this paper introduce a more rigorous metric: essential interactive capacity.
This definition is designed to be as restrictive as possible, assuming:
- No Exogenous Randomness: The coding scheme must be fully deterministic.
- Adaptive Speaker Order: The protocol must remain robust even if the order of who speaks when changes based on the conversation's history.
- Worst-Case Performance: The capacity must hold for any interactive protocol, not just an average case.
The central question is: what is the minimum fraction of Shannon capacity that can be guaranteed for any interactive protocol under these strict conditions?
The Rewind-if-Error Coding Scheme
To prove a lower bound, the authors develop a deterministic "rewind-if-error" coding strategy. The scheme operates through several innovative layers:
1. Simulation and Periodic Checking
Instead of applying heavy error correction to every individual bit, the parties simulate the interactive protocol in blocks. They proceed as if the channel were noiseless for a set duration and then pause to verify the integrity of the exchange.
2. Hierarchical Error Detection
The verification process is layered to balance efficiency and reliability:
- Layer 1: Uses deterministic extended-Hamming codes to catch and correct simple bit flips.
- Layer 2: Employs polynomial-based hashing to detect more complex errors that might have bypassed the first layer.
3. Derandomization via Channel Noise
A significant hurdle in deterministic coding is that efficient hashing typically requires random bits. To maintain the "essential" (deterministic) requirement without external randomness, the authors use the channel's own noise as a source of entropy. By applying a von Neumann extractor to the noise observed in the channel, they generate the necessary random bits for the hashing step. This "noise as a resource" approach allows the scheme to remain fully deterministic while achieving high asymptotic rates.
4. Repetition Coding
To ensure the baseline error rate is manageable for the hierarchical detection system, the authors first apply a standard repetition code. While this reduces the raw bit rate, it provides the stability needed for the higher-level "rewind" logic to function.
Key Results and Theoretical Implications
The primary contribution of the paper is the mathematical proof of a new lower bound for interactive capacity ($C_I$):
- The 3.02% Guarantee: For any Binary Memoryless Symmetric (BMS) channel, the essential interactive capacity is at least $0.0302 \times C_{Sh}$. This proves that the penalty for interactiveness is bounded; you are guaranteed to retain at least ~1/33rd of the standard Shannon capacity regardless of the protocol's complexity.
- The Low-Noise Limit: The authors demonstrate that as the channel becomes cleaner ($C_{Sh} \to 1$), the ratio $C_I / C_{Sh}$ approaches 1. This implies that in near-perfect channels, the overhead required for interactive error correction vanishes.
- Generalization: While the proof is initially constructed for the Binary Symmetric Channel (BSC), the authors extend the result to all BMS channels by showing that any BMS channel can be bounded by a BSC through the use of repetition coding.
Discussion and Future Directions
This work provides a critical floor for interactive communication, but it also highlights significant gaps in current understanding. While the lower bound of ~0.03 is a major theoretical step, the trivial upper bound remains at 0.5 (due to the necessity of turn-taking).
The authors suggest that the constant $0.0302$ is likely conservative and could be improved with more sophisticated coding architectures. Furthermore, finding a non-trivial upper bound—proving that interactive communication must lose a certain percentage of Shannon capacity—remains one of the most intriguing open questions in the field of information theory.
Summary updated