On May 18, 2023 at 15:00 EEST (note the time!), Elena Grigorescu (Purdue University, West Lafayette, IN, USA) will give a talk in the Logic Seminar (joint with the TCS Seminar).
Title: Local Codes for Insertion and Deletion Errors
Abstract:
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.