Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is $ {O}(k~\log ~{N})$ for constant k, and proposed an optimal… Click to show full abstract
Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is $ {O}(k~\log ~{N})$ for constant k, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k-deletion correcting codes remained open. Our key contribution is a major step towards a complete solution to this longstanding open problem for constant k. We present a k-deletion correcting code that has redundancy $8 {k}\log~{N} + {o}(\log~{N})$ when $ {k}= {o}(\sqrt {\log \log~{N}})$ and encoding/decoding algorithms of complexity $ {O}({N}^{2 {k}+1})$ .
