Revision #1 Authors: Boris Bukh, Venkatesan Guruswami, Johan HÃ¥stad

Accepted on: 29th February 2016 03:39

Downloads: 905

Keywords:

We consider codes over fixed alphabets against worst-case symbol

deletions. For any fixed $k \ge 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-\frac{2}{k+\sqrt k}$. In particular, for binary

codes, we are able to recover a fraction of deletions approaching

$1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414$.

Previously, even non-constructively the largest deletion

fraction known to be correctable with positive rate was

$1-\Theta(1/\sqrt{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-\Theta(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 $(\sqrt 2 -1)$ and $1/2$ for the limit of worst-case

deletions correctable by binary codes remains a tantalizing open

question.

Improvement of correctable deletion fraction from 1/3 to sqrt{2}-1 for binary case, and from 1-2/(k+1) to 1-2/(k+sqrt{k}) for alphabet size k, using a better choice of inner code in the original concatenation framework.

TR15-117 Authors: Boris Bukh, Venkatesan Guruswami

Publication: 21st July 2015 14:23

Downloads: 1414

Keywords:

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 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-\frac{2}{k+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-\Theta(1/\sqrt{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-\Theta(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.