Causal Erasure Channels

Raef Bassily, Adam D. Smith

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:

  1. 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.
  2. 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.

Comparison of capacity bounds for random, causal, and fully adversarial erasure channels.

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

Abstract

We consider the communication problem over binary causal adversarial erasure channels. Such a channel maps $n$ input bits to $n$ output symbols in $\{0,1,\wedge\}$, where $\wedge$ denotes erasure. The channel is causal if, for every $i$, the channel adversarially decides whether to erase the $i$th bit of its input based on inputs $1,...,i$, before it observes bits $i+1$ to $n$. Such a channel is $p$-bounded if it can erase at most a $p$ fraction of the input bits over the whole transmission duration. Causal channels provide a natural model for channels that obey basic physical restrictions but are otherwise unpredictable or highly variable. For a given erasure rate $p$, our goal is to understand the optimal rate (the capacity) at which a randomized (stochastic) encoder/decoder can transmit reliably across all causal $p$-bounded erasure channels. In this paper, we introduce the causal erasure model and provide new upper bounds and lower bounds on the achievable rate. Our bounds separate the achievable rate in the causal erasures setting from the rates achievable in two related models: random erasure channels (strictly weaker) and fully adversarial erasure channels (strictly stronger). Specifically, we show: - A strict separation between random and causal erasures for all constant erasure rates $p\in(0,1)$. - A strict separation between causal and fully adversarial erasures for $p\in(0,\phi)$ where $\phi \approx 0.348$. - For $p\in[\phi,1/2)$, we show codes for causal erasures that have higher rate than the best known constructions for fully adversarial channels. Our results contrast with existing results on correcting causal bit-flip errors (as opposed to erasures) [Dey et. al 2008, 2009], [Haviv-Langberg 2011]. For the separations we provide, the analogous separations for bit-flip models are either not known at all or much weaker.
BibTeX
@inproceedings{bassily2014causal,
  author = {Raef Bassily and Adam D. Smith},
  title = {{Causal Erasure Channels}},
  booktitle = {SODA},
  year = {2014},
  url = {https://openreview.net/forum?id=0ccqg4Gitx},
}
Figure