Corrections to “Reed Solomon Codes Against Adversarial Insertions and Deletions”
Roni Con, Amir Shpilka, Itzhak Tamo · IEEE Transactions on Information Theory · 2025
The purpose of this note is to correct an error made by Con et al. (2023), specifically in the proof of Theorem 9. Here we correct the proof but as a consequence we get a slightly weaker result. In Theorem9, we claimed that for integers k and n such that$k \lt n/9$, there exists an$[n,k]_{q}$RS code that can decode from$n-2k+1$insdel errors where$q = O\left ({{k^{5} \left ({{ \frac {en}{k-1} }}\right)^{4k-4}}}\right)$. Here we prove the following. Theorem 1: For integers n and$k \lt n/9$, there exists an$[n,k]_{q}$RS-code, where$q=O\left ({{k^{4} \cdot \left ({{\frac {4en}{4k-3}}}\right)^{4k-3}}}\right)$is a prime power, that can decode from$n - 2k + 1$adversarial insdel errors. Note that the exponent of n is$4k-3$whereas in Theorem 9 it is$4k-4$. For constant dimensional codes, the field size is of order$O(n^{4k-3})$, and in particular, for$k=2$the field size is of order$O(n^{5})$.