On the Zero-Error Capacity Threshold for Deletion Channels
The authors consider the zero-error capacity of deletion channels. Specifically, they consider the setting where they choose a codebook C consisting of strings of n bits, and their model of the channel corresponds to an adversary who may delete up to pn of these bits for a constant p. Their goal is to decode correctly without error regardless of the actions of the adversary. They consider what values of p allow non-zero capacity in this setting. They 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.