Coding against deletions in oblivious and online models

zbMATH Open1417.94102arXiv1612.06335MaRDI QIDQ4607922FDOQ4607922

Authors: Ray Li, Venkatesan Guruswami 

Publication date: 15 March 2018

Abstract: We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining $p_0^{(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 $p_0^{(adv)}gesqrt2-1$, and the trivial upper bound, $p_0^{(adv)}lefrac12$, is the best known. Perhaps surprisingly, we do not know whether or not $p_0^{(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 $p_0^{(obliv)}$ equals $1$. For online deletions, where the channel decides whether to delete bit $x_i$ based only on knowledge of bits $x_1{x}_{2}dots{x}_i$, define the deterministic zero-rate threshold for online deletions $p_0^{(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 $p_0^{(adv)}=frac12$ if and only if $p_0^{(on,d)}=frac12$.

Full work available at URL: https://arxiv.org/abs/1612.06335

Recommendations

• Deletion codes in the high-noise and high-rate regimes
• Efficiently decodable codes for the binary deletion channel
• An improved bound on the fraction of correctable deletions
• Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the $q$-ary Random Deletion Channel for Large $q$

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Linear codes (general theory) (94B05)

Cited In (4)

• Deletion codes in the high-noise and high-rate regimes
• A characterization of the capacity of online (causal) binary channels
• An improved bound on the fraction of correctable deletions
• Efficiently decodable codes for the binary deletion channel

This page was built for publication: Coding against deletions in oblivious and online models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607922)