Reed–Solomon (RS) codes are known to exist with optimal insertion–deletion (insdel) error-correcting capability — later work resolved the source paper's construction question for dimension k≥3k\ge 3 by attaining the half-Singleton bound for all kk — but the algorithmic and structural questions the source paper posed remain open: there is no efficient decoding algorithm for RS codes against a linear number of insdel errors (beyond dimension 22 or sublinear error counts), no list-decoding algorithm or list-decodability limits for RS codes in the insdel metric, and no study of how insdel distance behaves under taking the dual code. The problem is to resolve these surviving directions: efficient (unique and list) decoding of insdel RS codes with capability matching the known constructions, and the relation between a code's insdel distance and that of its dual.

Background

Insertion and deletion (insdel) errors are synchronization errors: symbols are spuriously inserted into or deleted from a transmitted word, so the receiver loses positional alignment. The edit distance between two words is the minimum number of insertions and deletions needed to transform one into the other; for equal-length words x,yx,y it equals 2(n−LCS(x,y))2(n-\mathrm{LCS}(x,y)), where LCS(x,y)\mathrm{LCS}(x,y) is the length of a longest common subsequence. The (minimum) insdel distance dd of a code is the minimum edit distance between distinct codewords, and a code can correct tt insdel errors if and only if d≥2t+2d\ge 2t+2. A Reed–Solomon (RS) code RSn,k(α1,…,αn)\mathrm{RS}_{n,k}(\alpha_1,\dots,\alpha_n) over a finite field Fq\mathbb{F}_q is the set of evaluation vectors (f(α1),…,f(αn))(f(\alpha_1),\dots,f(\alpha_n)) of polynomials ff of degree less than kk at nn distinct field elements; it is a linear code of length nn and dimension kk (an [n,k][n,k] code) with optimal Hamming distance n−k+1n-k+1. List decoding relaxes unique decoding: given a received word, output all codewords within a given insdel radius, aiming for a provably small output list. The dual code of a linear code is its orthogonal complement under the standard inner product; under the Hamming metric the dual of an RS code is again an RS code. For insdel codes the key limits are: the Singleton-type bound d≤2n−2k+2d\le 2n-2k+2; the half-Singleton bound of Cheng–Guruswami–Haeupler–Li (SODA 2021), namely that any linear code correcting a δ\delta fraction of deletions has rate at most (1−δ)/2+o(1)(1-\delta)/2+o(1); and the bound of Chen–Zhang (IEEE TIT 2022) that any [n,k][n,k] linear code with n>k>1n>k>1 satisfies d≤2n−2kd\le 2n-2k. Before 2019 the best known insdel capability of RS-type codes was the log⁡k+1n−1\log_{k+1} n-1 deletions of generalized RS subcodes due to Tonien–Safavi-Naini (2007). The source paper of this problem (Do Duc, Liu, Tjuawinata, Xing, IEEE TIT 2021) gave the first explicit two-dimensional (k=2k=2) RS families with insdel capability asymptotic to the code length, and closed by posing three open directions. The first — constructing RS codes of dimension k≥3k\ge 3 with capability substantially better than log⁡k+1n\log_{k+1} n — has since been resolved optimally: Con–Shpilka–Tamo (IEEE TIT 2023) proved that for 2k−1≤n2k-1\le n there exist [n,k][n,k] RS codes over fields of size O(n4k−2)O(n^{4k-2}) that correct n−2k+1n-2k+1 insdel errors, attaining the half-Singleton bound, with deterministic constructions over much larger fields; Con–Guo–Li–Zhang (ICALP 2025) showed random RS codes do so over linear-sized alphabets; Beelen–Con–Gruica–Montanucci–Yaakobi (IEEE TIT 2026) constructed full-length RS codes of any dimension k≥2k\ge 2 correcting q/(10k)q/(10k) insdel errors. What remains from the source paper is the algorithmic and structural half of its program, which no later work closes: decoding these high-capability codes efficiently, determining their list-decodability, and understanding duality in the insdel metric.

Problem Statement

As posed in the closing section of Do Duc–Liu–Tjuawinata–Xing (IEEE TIT 2021), with the construction direction since resolved, the surviving open problems for Reed–Solomon codes under the insertion–deletion metric are: (i) Decoding: construct an efficient decoding algorithm for [n,k][n,k] Reed–Solomon codes against tt insdel errors at the capability level the known code constructions achieve — in particular for dimension k≥3k\ge 3 and tt linear in nn (up to n−2k+1n-2k+1 errors, the half-Singleton capability), going beyond the known k=2k=2 deletion-only decoder of Singhvi and the list-recovery reduction of Banerjee–Con–Wachter-Zeh–Yaakobi (in list recovery, the decoder is given a small set of candidate symbols for each position instead of a single received symbol and must find all codewords picking one candidate per position), which is efficient only when t⋅k=O(n)t\cdot k=O(n) — and construct a list-decoding algorithm for Reed–Solomon codes under the insdel metric, determining the list-decodability limits of these codes in this metric. (ii) Duality: determine whether and how the insdel distance of a Reed–Solomon (or general linear) code relates to the insdel distance of its dual code, a structural question the source paper raised because no study of the relation between the insdel distance and the dual insdel distance existed and an investigation of this relation may reveal more insight into insdel Reed–Solomon codes, and which remains unexplored. The two parts share one objective, an algorithmic and structural theory of Reed–Solomon codes under insdel errors beyond code existence.

References

  1. Tai Do Duc, Shu Liu, Ivan Tjuawinata, Chaoping Xing. Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime. IEEE Transactions on Information Theory 67(5):2808–2820, 2021. DOI 10.1109/TIT.2021.3065618; arXiv:1909.03426, https://arxiv.org/abs/1909.03426
  2. Roni Con, Amir Shpilka, Itzhak Tamo. Reed Solomon Codes Against Adversarial Insertions and Deletions. IEEE Transactions on Information Theory 69, 2023. DOI 10.1109/TIT.2023.3237711; arXiv:2107.05699, https://arxiv.org/abs/2107.05699
  3. Roni Con, Zeyu Guo, Ray Li, Zihan Zhang. Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets. ICALP 2025. DOI 10.4230/LIPICS.ICALP.2025.60; arXiv:2407.07299, https://arxiv.org/abs/2407.07299
  4. Peter Beelen, Roni Con, Anina Gruica, Maria Montanucci, Eitan Yaakobi. Reed–Solomon Codes Against Insertions and Deletions: Full-Length and Rate-1/2 Codes. IEEE Transactions on Information Theory, 2026. DOI 10.1109/TIT.2025.3647216; arXiv:2501.11371, https://arxiv.org/abs/2501.11371
  5. Bocong Chen, Guanghui Zhang. Improved Singleton Bound on Insertion-Deletion Codes and Optimal Constructions. IEEE Transactions on Information Theory 68, 2022. DOI 10.1109/TIT.2022.3148185; arXiv:2105.02004, https://arxiv.org/abs/2105.02004
  6. Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li. Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SODA 2021, pp. 1–20. DOI 10.1137/1.9781611976465.1; arXiv:2007.09075, https://arxiv.org/abs/2007.09075
  7. Roni Con, Amir Shpilka, Itzhak Tamo. Optimal Two-Dimensional Reed–Solomon Codes Correcting Insertions and Deletions. IEEE Transactions on Information Theory, 2024. DOI 10.1109/TIT.2024.3387848; arXiv:2311.02771, https://arxiv.org/abs/2311.02771
  8. Shubhransh Singhvi. Optimally Decoding 2-D Reed–Solomon Codes Against Deletion Errors. IEEE Transactions on Information Theory, 2026. DOI 10.1109/TIT.2026.3656004; arXiv:2412.20771 (arXiv title: Optimally Decoding Two-Dimensional Reed–Solomon Codes Against Deletion Errors), https://arxiv.org/abs/2412.20771
  9. Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, Eitan Yaakobi. Decoding Insertions/Deletions via List Recovery. IEEE International Symposium on Information Theory (ISIT), 2025. DOI 10.1109/ISIT63088.2025.11195412; arXiv:2505.02452, https://arxiv.org/abs/2505.02452
  10. Shu Liu, Ivan Tjuawinata, Chaoping Xing. A Lower Bound on the List-Decodability of Insdel Codes. IEEE Transactions on Information Theory, 2023. DOI 10.1109/TIT.2023.3302862; arXiv:2211.06606, https://arxiv.org/abs/2211.06606
  11. Shu Liu, Ivan Tjuawinata, Chaoping Xing. On List Decoding of Insertion and Deletion Errors. arXiv:1906.09705, https://arxiv.org/abs/1906.09705
  12. Dongvu Tonien, Reihaneh Safavi-Naini. Construction of deletion correcting codes using generalized Reed–Solomon codes and their subcodes. Designs, Codes and Cryptography 42(2):227–237, 2007. DOI 10.1007/s10623-006-9032-7, https://doi.org/10.1007/s10623-006-9032-7
  13. Yulin Yang. Improved Johnson-type Bounds for Insertion-Deletion Codes. arXiv:2605.25090, https://arxiv.org/abs/2605.25090
  14. Roni Con, Dean Doron, João Ribeiro. The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity. arXiv:2607.03989, https://arxiv.org/abs/2607.03989
  15. Jingge Liu. Optimal RS Codes and GRS Codes Against Adversarial Insertions and Deletions and Optimal Constructions. IEEE Transactions on Information Theory, 2024. DOI 10.1109/TIT.2024.3398587, https://doi.org/10.1109/TIT.2024.3398587
  16. Roni Con, Amir Shpilka, Itzhak Tamo. Corrections to "Reed Solomon Codes Against Adversarial Insertions and Deletions". IEEE Transactions on Information Theory, 2025. DOI 10.1109/TIT.2025.3538114, https://doi.org/10.1109/TIT.2025.3538114