A Caltech Library Service

Optimal k​-Deletion Correcting Codes

Sima, Jin and Bruck, Jehoshua (2019) Optimal k​-Deletion Correcting Codes. In: International Symposium on Information Theory, 2019 (ISIT 2019), 7-12 July 2019, Paris, France.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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), 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 solution to this longstanding open problem. We present a k-deletion correcting code that has redundancy 8k log n + o(log n) and encoding/decoding algorithms of complexity O(n^{2k+1}) for constant k.

Item Type:Conference or Workshop Item (Paper)
Additional Information:The work was supported in part by NSF grants CCF-1816965 and CCF- 1717884.
Funding AgencyGrant Number
NSFCCF- 1717884
Record Number:CaltechAUTHORS:20190826-143512243
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98251
Deposited By: George Porter
Deposited On:26 Aug 2019 21:39
Last Modified:27 Aug 2019 06:05

Repository Staff Only: item control page