2016/12/19 by Guruswami, Venkatesan, Li, Ray · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1612.06335
We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining p0(adv), the zero-rate threshold of adversarial deletions, defined to be the supremum of all p for which there exists a code family with rate bounded away from 0 capable of correcting a fraction p of adversarial deletions. A recent construction of deletion-correcting codes [Bukh et al 17] shows that p0(adv) ≥ √(2)-1, and the trivial upper bound, p0(adv)≤(1)/(2), is the best known. Perhaps surprisingly, we do not know whether or not p0(adv) = 1/2. 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 pn deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction p < 1 of oblivious deletions, establishing that the associated zero-rate threshold p0(obliv) equals 1. For online deletions, where the channel decides whether to delete bit xi based only on knowledge of bits x1x2… xi, define the deterministic zero-rate threshold for online deletions p0(on,d) to be the supremum of p for which there exist deterministic codes against an online channel causing pn deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove p0(adv)=(1)/(2) if and only if p0(on,d)=(1)/(2).