Asymptotically Optimal Codes Correcting One Substring Edit
Yuting Li, Yuanyuan Tang, Hao Lou, University of Virginia, United States; Ryan Gabrys, University of California-San Diego, United States; Farzad Farnoud, University of Virginia, United States
Session:
Coding in Biology 2
Track:
17: Information and Coding in Biology
Location:
Sigma/Delta
Presentation Time:
Mon, 8 Jul, 15:35 - 15:55
Session Chair:
Emanuele Viterbo, Monash University
Abstract
THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. The substring edit error is the operation of replacing a substring u of x with another string v, where the lengths of u and v are bounded by a given constant k. It encompasses localized insertions, deletions, and substitutions within a window. Codes correcting one substring edit have redundancy at least log n + k. In this paper, we construct codes correcting one substring edit with redundancy log n + O(log log n), which is asymptotically optimal. The full version of this paper is available online.