Introduction
In classical information theory, noise models typically fall into two categories: the "optimistic" random noise model (Shannon) and the "pessimistic" worst-case adversarial model (Hamming). In the Shannon model, bits are erased independently with probability $p$, while in the Hamming model, an omniscient adversary erases any $pn$ bits to maximize decoding error.
Raef Bassily and Adam Smith's paper, "Causal Erasure Channels," explores the middle ground by introducing the causal erasure channel. In this model, an adversary decides whether to erase a bit based solely on the bits transmitted up to that point, without knowledge of future bits.
The Causal Adversary
The causal adversary operates in an "online" fashion. For each bit $i$ in a codeword of length $n$, the channel makes an erasure decision based on the prefix $x_1, \dots, x_i$. This model is more realistic for many real-world scenarios where channels exhibit bursty or adaptive behavior but cannot "see the future." The central goal of the paper is to determine the capacity $C_p$—the maximum achievable rate of reliable communication—under such constraints.
Methodology
The authors employ two primary theoretical techniques to bound the capacity:
- Upper Bounds (Impossibility): They introduce the "Wait-Push" strategy. Here, the adversary waits to observe a prefix of the codeword to narrow down the possible messages. Once the candidate list is sufficiently small, the adversary "pushes" the decoder toward an incorrect message by erasing bits where the true codeword differs from a selected fake codeword.
- Lower Bounds (Achievability): Using a random coding argument within a two-step model (message followed by redundancy), the authors analyze the size of a "forbidden ball." This set represents points around a codeword that could lead to decoding errors; proving this ball is small enough ensures the existence of good codes.
Key Results and Theoretical Bounds
The paper establishes that causality is a significant constraint that allows for higher transmission rates than the fully adversarial model, particularly at low erasure rates.
As shown in Figure 1, several critical insights emerge:
- The 1/2 Capacity Crash: Unlike the random erasure channel, where capacity is $1-p$ and remains positive until $p=1$, the causal erasure capacity drops to zero exactly at $p = 1/2$. This represents a fundamental limit where the adversary can effectively spoof messages.
- Strict Separation: The capacity of the causal channel lies strictly between the random erasure channel (magenta line) and the best-known bounds for the fully adversarial channel (green and red lines).
- Efficiency at Low Rates: For $p \to 0$, causal channels require significantly less redundancy ($O(pn)$ bits) compared to fully adversarial channels ($\Theta(np \ln(1/p))$).
- The $\phi$ Threshold: For erasure rates below $\phi \approx 0.348$, there is a provable gap where causal capacity exceeds the best possible rate for a fully adversarial channel.
Conclusion and Future Directions
The work demonstrates that "online" knowledge significantly limits an adversary's power compared to "offline" knowledge. While the paper provides strong existential proofs for good codes, the lower bounds remain non-constructive. Future research is needed to develop explicit, polynomial-time algorithms for these rates and to extend these results from erasures to bit-flip errors, which present a much more complex challenge.
Summary updated