Roni Con - Linear and Reed-Solomon Codes Correcting Insertions and Deletions

An important model that has been considered ever since Shannon's work is that of synchronization errors. These are errors that affect the length of the received word.
The most common model for studying synchronization errors is the insertion-deletion model (insdel for short): an insertion error is when a new symbol is inserted between two symbols of the transmitted word. A deletion is when a symbol is removed from the transmitted word.

Efficient codes that can handle these errors hold immense value in DNA-based storage---a novel and captivating storage medium that has recently attracted significant attention. 

Linear codes are desirable for many reasons: they have a compact representation (they are determined by their generating matrix), they are efficiently encodable, and in some settings, we even have linear codes with linear encoding and decoding time, and often they are simpler to analyze. Among linear codes, Reed--Solomon (RS) codes stand out; Among their applications are QR codes, secret sharing schemes, space transmission, encoding data on CDs,  and more. As such, it is an important problem to understand whether they can also decode from insdel errors.

In this talk, I will survey recent works that study the performance of linear codes against insertion-deletion errors. I will also show that there exist Reed-Solomon (RS) codes capable of achieving the best rate-distance tradeoff achievable by a linear code against insdel errors. Finally, I will conclude by discussing several interesting open questions.

This talk is based on joint work with Amir Shpilka and Zachi Tamo