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 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 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 study the capacity at which a randomized (stochastic) encoder/decoder can transmit reliably across all causal p- bounded erasure channels.

In this talk, I will present the causal erasure model and give new upper and lower bounds on the capacity. Our bounds separate the capacity in the causal erasures setting from the capacity 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 existence of codes for causal erasures that achieve strictly higher rates than the best known codes for fully adversarial channels.

Our results contrast with existing results on correcting causal bit-flip errors (as opposed to erasures) [Dey et. al 08, 09], [Haviv-Langberg 11] . For the separations we provide, the analogous separations for bit-flip models are either not known at all or much weaker.

** This talk is based on a joint work with Adam Smith (Pennsylvania State University). It will appear in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.