SIGACT News Complexity Theory Column 126 Locally Decodable Codes for Insertions and Deletions

Local decoding enables fast recovery of individual symbols of a message, even in the presence of errors. Locally decodable codes that can withstand Hamming errors are foundational in theoretical computer science, with deep connections to program checking, probabilistically checkable proofs, private information retrieval, and data structures. More recently, the literature has expanded to address a much more challenging type of errors: insertions and deletions. These synchronization errors may cause misalignment in the data, and are especially relevant to emerging applications in DNA storage technologies. In this article, we survey recent advances on local decoding in the presence of synchronization errors, highlight key techniques, and state several open problems.