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

# Technical Program

## Paper Detail

 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)$.