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 − 2 k + k . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1 ( 2 + 1 ) = 2 − 1 0 414 . 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 ( 2 − 1 ) and 1 2 for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.