Correcting Deletions: Fundamental Questions and Surprising Applications

Error-correcting codes are central to information theory and theoretical computer science, enabling reliable communication in the presence of noise. Classical results focus primarily on substitutions and erasures, and over the years elegant constructions have emerged that meet, or closely approach, the optimal rate-noise tradeoffs in these settings. A natural and equally fundamental error model involves synchronization errors, such as insertions and deletions. These errors, already studied in the 1960s, cause misalignment between sender and receiver and arise in various modern technologies, with DNA-based data storage being a particularly compelling example. Despite decades of attention, fully characterizing the capacity of synchronization channels and constructing practical, near-optimal codes for them remain major open challenges.

In this talk, I will survey recent progress on coding for synchronization channels and then focus on the performance of linear and Reed–Solomon codes under insertions and deletions, demonstrating that well-structured algebraic codes can, perhaps unexpectedly, correct a significant amount of synchronization noise. I will then highlight a surprising application of these ideas in secret sharing. Finally, I will discuss how input-correlated insertion/deletion channels naturally arise in DNA-based data storage, an emerging ultra-dense archival technology, and present capacity theorems and efficient coding schemes tailored to an important class of such channels.

Roni Con is a postdoctoral researcher at the Technion, hosted by Prof. Eitan Yaakobi. In Spring 2024, he was a Simons Research Fellow in the program Error-Correcting Codes: Theory and Practice at the Simons Institute for the Theory of Computing. He completed his Ph.D. in October 2023 at Tel Aviv University under the supervision of Profs. Amir Shpilka and Zachi Tamo. His research focuses on error-correcting codes and information theory, with applications to synchronization-error channels, modern storage systems, and cryptography.