  We consider the zero-error capacity of deletion channels. Specifically, we
consider the setting where we choose a codebook ${\cal C}$ consisting of
strings of $n$ bits, and our model of the channel corresponds to an adversary
who may delete up to $pn$ of these bits for a constant $p$. Our goal is to
decode correctly without error regardless of the actions of the adversary. We
consider what values of $p$ allow non-zero capacity in this setting. We suggest
multiple approaches, one of which makes use of the natural connection between
this problem and the problem of finding the expected length of the longest
common subsequence of two random sequences.
