Title: Local Codes for Insertion and Deletion Errors
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error.
In this talk I will describe our recent results on LDCs and their variants, when the errors are in the form of insertions and deletions (a.k.a. synchronization errors), rather than classical Hamming errors. Local codes against insertions and deletions are well-motivated by recent progress on DNA storage technologies. I will conclude with several open problems. The talk will be self-contained. (Based on joint work with Alex Block, Jeremiah Blocki, Kuan Cheng, Shubhang Kulkarni, Xin Li, Yu Zheng, Minshen Zhu.)
The talk will take place physically at FMI (Academiei 14), Council Hall.