Time: Sunday, December 11st, 2022, 14:30-15:30
Room: Taub 601
Speaker: Roni Con
Affiliation: Tel Aviv University
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.