Causal Erasure Channels

Raef Bassily, Adam D. Smith

This paper, "Causal Erasure Channels" by Raef Bassily and Adam Smith, explores a middle ground in coding theory between the "optimistic" world of random noise and the "pessimistic" world of worst-case adversarial noise.

TL;DR

The authors introduce the causal erasure channel, where an adversary decides whether to erase a bit based only on the bits transmitted so far. They prove that the capacity of this channel lies strictly between random and fully adversarial models, notably showing that capacity hits zero at an erasure rate of $p = 1/2$.

What Problem Does This Paper Address?

In classical information theory, we usually model noise in two ways:

  1. Random (Shannon): Bits are erased independently with some probability $p$. This is often too optimistic for real-world bursty or variable channels.
  2. Fully Adversarial (Hamming): An all-knowing adversary sees the entire codeword and chooses the "worst" $pn$ bits to erase. This is often too pessimistic, as real-world channels cannot "see the future."

The authors address the gap by defining causal adversaries. These channels are online: for every bit $i$, the channel decides to erase it based on bits $1$ through $i$, without knowing bits $i+1$ to $n$. The goal is to determine the "capacity" ($C_p$)—the maximum rate at which we can transmit information reliably—under this constraint.

Methods

The paper employs two primary theoretical approaches to sandwich the true capacity:

  • Upper Bounds (Impossibility): The authors use a "Wait-Push" strategy. The adversary "waits" to observe a prefix of the codeword to narrow down the possible messages. Once it has a small enough "candidate list," it "pushes" the decoder toward a fake message by erasing bits where the true codeword and a selected fake codeword differ.
  • Lower Bounds (Achievability): They use a random coding argument within a "two-step" model. In this model, the message is sent first, followed by redundancy. The authors analyze the size of a "forbidden ball"—the set of points around a codeword that could lead to a decoding error—to prove that a good code must exist.

Datasets

As a theoretical work in information theory and coding, this paper does not use empirical datasets. Instead, it relies on mathematical proofs, asymptotic analysis, and comparisons against established theoretical bounds like the Gilbert-Varshamov (GV) bound and the Plotkin bound.

Key Insights and Ideas

  • Causality is a Significant Constraint: An online adversary is strictly weaker than a global one. This allows for higher transmission rates than worst-case models suggest, especially at low erasure rates.
  • The 1/2 Capacity Crash: Unlike random erasure channels (where capacity is $1-p$ and remains non-zero until $p=1$), causal erasure capacity drops to zero exactly at $p = 1/2$. This is a "hard limit" imposed by the adversary's ability to spoof messages.
  • Redundancy Scaling: For very low erasure rates ($p \to 0$), causal channels require only $O(pn)$ bits of redundancy. In contrast, fully adversarial channels require $\Theta(np \ln(1/p))$. This suggests that causal models are much more efficient for high-rate communication.
  • Separation of Models: The paper proves a "strict separation" between all three models (random, causal, and fully adversarial) for a wide range of erasure rates.

Key Results

The main quantitative findings are summarized in the paper's Figure 1:

  • Upper Bound: $C_p \leq (1 - 2p)^+$. This matches the Plotkin bound for codes with minimum distance $pn+1$, but requires a new proof because the adversary is causal.
  • Lower Bound: The authors define a function $R_L(p)$ that is strictly greater than the best-known adversarial bounds (the GV bound) for $p < 1/2$.
  • The $\phi$ Threshold: For $p < \phi \approx 0.348$, there is a clear, provable gap where causal capacity is higher than the best possible rate for a fully adversarial channel.

Limitations and Future Work

  • Non-Constructive Lower Bounds: The lower bounds are proven via random coding, meaning the paper shows that "good codes exist" but does not provide an explicit, polynomial-time algorithm to construct them or decode them at those rates.
  • The Gap: There remains a gap between the upper bound $(1-2p)$ and the lower bound $R_L(p)$ for $p \in (0, 1/2)$. Closing this gap is a primary direction for future research.
  • Bit-Flips vs. Erasures: The authors note that while they achieved strong results for erasures, the analogous results for bit-flip errors (where bits are toggled rather than deleted) are much harder to prove and remain largely open.

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, ∧}, where ∧ denotes erasure. The channel is causal if, for every i, the channel adversarially decides whether to erase the ith 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 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 (impossibility results) and lower bounds (analyses of codes) 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 ∊ (0,1). In particular, we show that the capacity of causal erasure channels is 0 for p ≥ 1/2 (while it is nonzero for random erasures). A strict separation between causal and fully adversarial erasures for p ∊ (0, φ) where φ ≈ 0.348. For p ∊ [φ, 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) [10, 9, 7, 4, 11]. 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},
}

Loading related content...

Figure