Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Coding Theory: Reed-Solomon Codes Against Adversarial Insertions and Deletions
event speaker icon
Roni Con (Tel-Aviv University)
event date icon
Sunday, 11.12.2022, 14:30
event location icon
Taub 601
The task of constructing codes against adversarial insertions and deletions (insdel) has recently received much attention. In this work, we study the performance of Reed-Solomon codes against insdel errors. We prove that there are Reed-Solomon codes that achieve the half-Singleton bound. In other words, there are optimal Reed-Solomon codes also against insdel errors. We also give a set of evaluation points that define a Reed-Solomon code that achieves this bound. As the field size that we get grows very fast, our construction runs in polynomial time only for very small values of $k$, the dimension of the code. We also explicitly construct two-dimensional Reed-Solomon codes over a field of size $O(n^4)$ that can correct from $n-3$ insdel errors. Earlier constructions required an exponential field size. Joint work with Amir Shpilka and Zachi Tamo. Roni Con received the B.Sc. and M.Sc. degrees in applied mathematics from Bar-Ilan University in 2012 and 2016, respectively. He is currently pursuing a Ph.D. degree at the Computer Science Department, Tel Aviv University, under the supervision of Amir Shpilka and Itzhak Tamo. His research interests include error-correcting codes and their applications to theoretical computer science, DNA-based storage, and distributed storage systems.