A Caltech Library Service

On Optimal k-Deletion Correcting Codes

Sima, Jin and Bruck, Jehoshua (2021) On Optimal k-Deletion Correcting Codes. IEEE Transactions on Information Theory, 67 (6). pp. 3360-3375. ISSN 0018-9448. doi:10.1109/TIT.2020.3028702.

[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) 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 8k log N + o(log N) when k = o(√log log N) and encoding/decoding algorithms of complexity O(n^(2k+1)).

Item Type:Article
Related URLs:
URLURL TypeDescription
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2020 IEEE. Manuscript received October 15, 2019; revised June 4, 2020; accepted September 8, 2020. Date of publication October 5, 2020; date of current version May 20, 2021. This work was supported in part by NSF grants CCF-1717884 and CCF-1816965. This paper was presented in part at the 2019 IEEE International Symposium on Information Theory. The authors would like to thank the anonymous reviewers for their valuable suggestions that greatly improved the clarity and the organization of the paper.
Funding AgencyGrant Number
Subject Keywords:Deletion codes, Varshamov-Tenengoltz code
Issue or Number:6
Record Number:CaltechAUTHORS:20201008-083807800
Persistent URL:
Official Citation:J. Sima and J. Bruck, "On Optimal k-Deletion Correcting Codes," in IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3360-3375, June 2021, doi: 10.1109/TIT.2020.3028702
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105909
Deposited By: George Porter
Deposited On:08 Oct 2020 18:11
Last Modified:26 May 2021 22:14

Repository Staff Only: item control page