All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-S7-T4.3
Paper Title Optimal Codes Correcting Localized Deletions
Authors Rawad Bitar, Serge Kas Hanna, Technical University of Munich, Germany; Nikita Polyanskii, Technical University of Munich, and Skolkovo Institute of Science and Technology, Germany; Ilya Vorobyev, Skolkovo Institute of Science and Technology, Russia
Session D4-S7-T4: Insertions/Deletions III
Chaired Session: Friday, 16 July, 00:00 - 00:20
Engagement Session: Friday, 16 July, 00:20 - 00:40
Abstract We consider the problem of constructing codes that can correct deletions that are localized within a certain part of the codeword that is unknown a priori. Namely, the model that we study is when at most $k$ deletions occur in a window of size $k$, where the positions of the deletions within this window are not necessarily consecutive. Localized deletions are thus a generalization of burst deletions that occur in consecutive positions. We present novel explicit codes that are efficiently encodable and decodable and can correct up to $k$ localized deletions. Furthermore, these codes have $\log n+\mathcal{O}(k \log^2 (k\log n))$ redundancy, where $n$ is the length of the information message, which is asymptotically optimal in $n$ for $k=o(\log n/(\log \log n)^2)$.