Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-117 | 29th February 2016 03:39

#### An improved bound on the fraction of correctable deletions Revision #1
Authors: Boris Bukh, Venkatesan Guruswami, Johan Håstad
Accepted on: 29th February 2016 03:39
Keywords:

Abstract:

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.

Changes to previous version:

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.

### Paper:

TR15-117 | 21st July 2015 14:22

#### An improved bound on the fraction of correctable deletions

TR15-117
Authors: Boris Bukh, Venkatesan Guruswami
Publication: 21st July 2015 14:23
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint
{"ft_lang_label":"__label__en","ft_lang_prob":0.8765473,"math_prob":0.9834125,"size":2185,"snap":"2020-45-2020-50","text_gpt3_token_len":560,"char_repetition_ratio":0.13296653,"word_repetition_ratio":0.7407407,"special_character_ratio":0.2508009,"punctuation_ratio":0.07692308,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9847449,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-29T07:29:53Z\",\"WARC-Record-ID\":\"<urn:uuid:95796f6b-c390-4038-a1f7-9cc858884172>\",\"Content-Length\":\"23303\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:30c56fb6-6963-409a-a831-09dcc01efec2>\",\"WARC-Concurrent-To\":\"<urn:uuid:16ae1657-c1b7-4538-8ea3-db361320a9e3>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/report/2015/117/\",\"WARC-Payload-Digest\":\"sha1:25552HSRSR6IU62HIVXGRTQQUGUWF53A\",\"WARC-Block-Digest\":\"sha1:GRDA7LIFXQ2WBAFD67NBUVH2SKORRDMR\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141197278.54_warc_CC-MAIN-20201129063812-20201129093812-00421.warc.gz\"}"}