Locally Decodable/Correctable Codes for Insertions and Deletions

Understand

Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-correction capabilities, as well as efficient encoding and decoding algorithms.

• In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with super-efficient decoding algorithms.
• These have led to the well-studied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs).
• Inspired by these notions, Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions.