A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels

Assaf Ben-Yishai, Young-Han Kim, Or Ordentlich, Ofer Shayevitz

TL;DR

This paper establishes a concrete lower bound for the "essential interactive capacity" of binary memoryless symmetric (BMS) channels, proving it is at least 3.02% of the standard Shannon capacity. The authors achieve this by designing a deterministic, layered "rewind-if-error" coding scheme that handles adaptive speaker orders without requiring pre-shared randomness.

What Problem Does This Paper Address?

In classical information theory, Shannon capacity tells us the maximum rate at which Alice can send a pre-determined message to Bob. However, human conversation and many computing tasks are interactive: what Alice says next depends on what Bob just said.

Interactive communication is "one-shot" and fragile. Unlike one-way messaging, where you can use massive block codes to ensure reliability, interactive protocols require bits to be decoded almost instantly so the "conversation" can continue. If a single bit is flipped and goes undetected, the two parties' internal states diverge, rendering the rest of the interaction useless (imagine a remote chess game where one player thinks a knight moved, but the other thinks it was a bishop).

While it was known that interactive capacity is a non-zero fraction of Shannon capacity, the exact value of that fraction—and how to achieve it deterministically without assuming a fixed order of speakers—remained an open question.

Methods

The authors propose a layered rewind-if-error coding scheme. The core idea is to simulate the interactive protocol in small blocks. After each block, the parties perform error detection. If an error is found, they "rewind" their state and re-transmit.

Key technical components include:

  • Hierarchical Error Detection: The first layer uses extended-Hamming codes for efficient error detection. Higher layers use randomized polynomial-based hashing to catch errors that might have slipped through the lower levels.
  • Adaptive Speaker Handling: To account for protocols where the speaker order isn't fixed (e.g., Alice might speak twice in a row depending on the data), the scheme uses a "bit-vs-bit" alternating order, inserting dummy bits when necessary. This imposes a 1/2 rate penalty but ensures the scheme works for any protocol.
  • Derandomization: While the initial scheme relies on random bits for hashing, the authors show how to extract these bits from the noisy channel itself. This makes the final scheme fully deterministic, relying only on the channel's inherent noise as a source of randomness.

Datasets

As a theoretical work in information theory, this paper does not use empirical datasets. Instead, it evaluates the proposed coding scheme against mathematical channel models:

  • Binary Symmetric Channel (BSC): The simplest model where bits are flipped with a fixed probability $\epsilon$.
  • Binary Memoryless Symmetric (BMS) Channels: A broad family of channels (including the Binary Erasure Channel and BiAWGN) that satisfy certain symmetry properties.

Key Insights and Ideas

  • The "Cost of Interactiveness": The paper quantifies the overhead of interaction. Even under the most restrictive conditions (deterministic coding, unknown speaker order), you only lose about 97% of the Shannon capacity. While that sounds like a lot, in complexity theory, any constant fraction is a major win.
  • Deterministic Robustness: Most previous interactive coding schemes assumed Alice and Bob shared a "random seed" (public randomness). This paper proves that the channel's own noise is "good enough" to provide the randomness needed for robust error detection.
  • Bhattacharyya Extremes: To move from the simple BSC to the entire BMS family, the authors use the Bhattacharyya parameter (a measure of channel quality). They show that the worst-case performance for their scheme occurs at the "extremes" of this parameter, allowing the BSC bound to apply universally.

Key Results

  • The 0.0302 Bound: The main result is that for any BMS channel, the essential interactive capacity $C_I$ satisfies: $$\frac{C_I}{C_{Sh}} \geq 0.0302$$ where $C_{Sh}$ is the Shannon capacity.

  • Asymptotic Optimality: The authors show that as the channel becomes "cleaner" (noise goes to zero), the interactive capacity approaches the theoretical maximum of 1 (or 0.5 when accounting for the speaker-order penalty).

  • Structured Coding: Unlike previous "tree code" based proofs which are often non-constructive, this scheme uses practical components like Hamming codes and polynomial hashes.

Limitations and Future Work

  • Tightness of the Bound: The authors acknowledge that 3.02% is likely a very conservative lower bound. There is a massive gap between this result and the trivial upper bound of 50%.
  • Complexity: While the scheme is deterministic and structured, the layered "rewind" logic is computationally intensive to implement in real-time hardware compared to standard one-way codes.
  • Clean Channel Limit: The behavior of the bound in the limit of a "very clean channel" remains an intriguing open question; the authors suggest their current bound might be improved by using different coding strategies for low-noise environments.

Summary updated

Abstract

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.
BibTeX
@article{benyishai2021lower,
  author = {Assaf Ben-Yishai and Young-Han Kim and Or Ordentlich and Ofer Shayevitz},
  title = {{A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  doi = {10.1109/tit.2021.3104964},
}
Figure