We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining @math , the zero-rate threshold of adversarial deletions, defined to be the supremum of all @math for which there exists a code family with rate bounded away from 0 capable of correcting a fraction @math of adversarial deletions. A recent construction of deletion-correcting codes [ 17] shows that @math , and the trivial upper bound, @math , is the best known. Perhaps surprisingly, we do not know whether or not @math . In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of @math deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction @math of oblivious deletions, establishing that the associated zero-rate threshold @math equals @math . For online deletions, where the channel decides whether to delete bit @math based only on knowledge of bits @math , define the deterministic zero-rate threshold for online deletions @math to be the supremum of @math for which there exist deterministic codes against an online channel causing @math deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove @math if and only if @math .
We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed @math , we construct a family of codes over alphabet of size @math with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching @math . In particular, for binary codes, we are able to recover a fraction of deletions approaching @math . Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was @math , and around @math for the binary case. Our result pins down the largest fraction of correctable deletions for @math -ary codes as @math , since @math is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between @math and @math for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.