| Paper ID | D4-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)$.
|
