ECCC-Report TR15-117https://eccc.weizmann.ac.il/report/2015/117Comments and Revisions published for TR15-117en-usMon, 29 Feb 2016 03:39:27 +0200
Revision 1
| An improved bound on the fraction of correctable deletions |
Boris Bukh,
Venkatesan Guruswami,
Johan HÃ¥stad
https://eccc.weizmann.ac.il/report/2015/117#revision1We 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.Mon, 29 Feb 2016 03:39:27 +0200https://eccc.weizmann.ac.il/report/2015/117#revision1
Paper TR15-117
| An improved bound on the fraction of correctable deletions |
Boris Bukh,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2015/117We 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.Tue, 21 Jul 2015 14:23:34 +0300https://eccc.weizmann.ac.il/report/2015/117