Graph explorer

Causal Erasure Channels

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