file.pdf (131.5 kB)

An improved bound on the fraction of correctable deletions

Download (131.5 kB)
journal contribution
posted on 01.06.2015 by Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed k≥2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching 1−2k+1. In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/3. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was 1−Θ(1/k√), and around 0.17 for the binary case.

Our result pins down the largest fraction of correctable deletions for k-ary codes as 1−Θ(1/k), since 1−1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known.

Closing the gap between 1/3 and 1/2 for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.