Published July 2019
| Accepted Version + Submitted
Book Section - Chapter
Open
Optimal k-Deletion Correcting Codes
- Creators
-
Sima, Jin
-
Bruck, Jehoshua
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), 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.
Additional Information
© 2019 IEEE. The work was supported in part by NSF grants CCF-1816965 and CCF-1717884.Attached Files
Accepted Version - K_deletion_codes_Jin_Sima.pdf
Submitted - 1910.12247.pdf
Files
1910.12247.pdf
Files
(547.6 kB)
Name | Size | Download all |
---|---|---|
md5:e6217cd0b3b1aa6cc949937af8d632ea
|
246.6 kB | Preview Download |
md5:f06ca59a9728a49b4247983fc98bd3d4
|
300.9 kB | Preview Download |
Additional details
- Eprint ID
- 98251
- DOI
- 10.1109/ISIT.2019.8849750
- Resolver ID
- CaltechAUTHORS:20190826-143512243
- NSF
- CCF-1816965
- NSF
- CCF-1717884
- Created
-
2019-08-26Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field