Abstract
The essential interactive capacity of a discrete memoryless channel is defined as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel using a deterministic coding scheme. Unlike previous definitions, this approach makes no assumptions regarding the order of speakers—which may be adaptive—and forbids the use of private or public randomness. This paper demonstrates that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 times its Shannon capacity. This lower bound is achieved through a layered coding scheme utilizing extended-Hamming codes and error detection, initially designed for the binary symmetric channel (BSC) and subsequently extended to the entire BMS family using extremes of the Bhattacharyya parameter.
Introduction
In classical information theory, Shannon's capacity defines the fundamental limit for one-way communication: the maximum rate at which Alice can transmit a message to Bob. However, many modern computational and communication tasks are inherently interactive. In these scenarios, the message Alice sends at any given moment depends on the information she has already received from Bob.
Interactive communication is uniquely fragile. In one-way messaging, large block codes can be used to ensure high reliability. In contrast, interactive protocols require bits to be decoded almost immediately to maintain the flow of the "conversation." If a single bit is flipped and remains undetected, the internal states of the two parties can diverge, causing the entire interaction to fail. This paper addresses the challenge of establishing a concrete lower bound for the rate of such interactions under strict deterministic constraints.
Defining Essential Interactive Capacity
The authors introduce the concept of essential interactive capacity ($C_I$). This definition is more restrictive than previous models in three key ways:
- Deterministic Coding: The scheme cannot rely on pre-shared (public) or private randomness.
- Adaptive Speaker Order: The scheme must function even if the protocol does not specify who speaks when (e.g., Alice may speak multiple times in a row based on her local data).
- Channel Dependency: The capacity is a function of the channel model alone, rather than the specific protocol being simulated.
The Layered "Rewind-if-Error" Scheme
To achieve the lower bound, the authors propose a hierarchical coding architecture. The simulation of the interactive protocol is divided into small blocks, and the parties employ a "rewind-if-error" strategy.
Hierarchical Error Detection
The scheme operates in layers. The first layer utilizes extended-Hamming codes for efficient, low-overhead error detection. If an error is detected at this level, the parties immediately attempt to correct it. To catch more sophisticated errors that might bypass the Hamming codes, higher layers employ randomized polynomial-based hashing.
Handling Adaptive Speakers
To manage protocols where the speaker order is unknown or adaptive, the scheme adopts a "bit-vs-bit" alternating order. By inserting dummy bits when the protocol does not require a specific party to speak, the scheme ensures a consistent structure. While this imposes a 1/2 rate penalty, it provides the robustness necessary to handle any arbitrary interactive protocol.
Derandomization via Channel Noise
A significant hurdle in deterministic interactive coding is the need for randomness in hashing. The authors overcome this by extracting randomness from the noisy channel itself. By using the inherent stochasticity of the channel as a source of bits, the authors transform what was originally a randomized scheme into a fully deterministic one.
Theoretical Results
The study evaluates the proposed scheme against Binary Memoryless Symmetric (BMS) channels, a broad class that includes the Binary Symmetric Channel (BSC) and the Binary Erasure Channel (BEC).
The 0.0302 Bound
The primary result of the paper is the establishment of a universal lower bound. For any BMS channel, the essential interactive capacity $C_I$ relates to the Shannon capacity $C_{Sh}$ as follows:
$$\frac{C_I}{C_{Sh}} \geq 0.0302$$
While this suggests that interaction costs approximately 97% of the available Shannon capacity, the existence of a constant, non-zero fraction is a major theoretical milestone. It proves that reliable, deterministic interaction is possible at a fixed rate regardless of the channel's noise level (within the BMS family).
Bhattacharyya Extremes
To generalize the results from the simple BSC to all BMS channels, the authors utilize the Bhattacharyya parameter, a measure of channel quality. They demonstrate that the worst-case performance for their specific coding scheme occurs at the extremes of this parameter, allowing the bound derived for the BSC to serve as a global lower bound for the entire BMS family.
Conclusion and Future Work
This work provides a constructive proof for interactive capacity using structured components like Hamming codes and polynomial hashes, moving beyond the non-constructive "tree code" proofs common in earlier literature.
However, the authors note that the 0.0302 bound is likely conservative. There remains a significant gap between this lower bound and the theoretical upper bound of 0.5 (the latter being limited by the speaker-order penalty). Future research may focus on tightening this bound, particularly in "clean" channels with low noise, and reducing the computational complexity of the layered rewind logic for practical hardware implementation.
Summary updated