CS Paper Radar

Insdel Decoding Algorithms for Maximum Distance Separable Codes

Bencheng Fan, Margreta Kuijper, Jingge Zhu

cs.IT ·submitted 2026-10-25 19:11 UTC · v1

Abstract

In this paper, we focus on decoding MDS linear block codes for insdel errors. Building on our recent work for two-dimensional Reed-Solomon codes, we present a decoding algorithm for bounded distance decoding for the general insertion-and-deletion scenario that can be used for any MDS code of rate at most half. Our algorithm employs a sliding window and has a time complexity smaller than brute-force decoding. In particular, for optimal Reed-Solomon codes, it corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.

Closest papers

Nearest neighbours by meaning across the whole index.

Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound

cs.IT ·2026-10-11 ·Bencheng Fan, Margreta Kuijper, Jingge Zhu
similarity 0.89
Abstract

In this paper, we focus on decoding optimal Reed-Solomon codes of dimension two for insdel errors up to the half-Singleton bound. We present a decoding algorithm for the general insertion-and-deletion scenario with a time complexity smaller than brute-force decoding. Our algorithm corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.

0.40

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

cs.IT math.CO ·2026-10-16 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.74
Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.

0.07

Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps

cs.CC cs.IT ·2026-10-06 ·Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
publishedhighly cited similarity 0.74
Abstract

Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.

0.51

On Twisted Roth-Lempel Codes

cs.IT ·2026-09-15 ·Huiyue Lei, Haojie Gu, Jun Zhang, Haiyan Zhou
similarity 0.74
Abstract

In 1989, Roth and Lempel constructed a well-known family of non-Reed-Solomon maximum distance separable (MDS) codes. For decades, this family of codes has attracted extensive research attention due to its algebraic structure, low-complexity decoding, and broad applications in cryptography and data storage. In this paper, we present a class of twisted Roth-Lempel codes. We investigate their minimum distance, MDS and NMDS properties. Specifically, we determine the necessary and sufficient conditions for the TRL codes to have minimum distance n-k or n-k+1. Furthermore, we determine the necessary and sufficient conditions for the TRL code to be an MDS or NMDS code. Moreover, we show that the dimension of the Schur square of the TRL code is at least 2k+1, and thus the TRL code is a non-RS code inequivalent to the corresponding RL code.

0.15

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.71
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios

cs.IT ·2026-11-16 ·Runqing Qiu, Shixin Zhu, Yang Li, San Ling
similarity 0.71
Abstract · 16 pages

Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $Θ(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.

0.12

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

cs.IT cs.CC ·2026-10-26 ·Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami
publishedhighly cited similarity 0.69
Abstract

For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optimal list-size of $O(\frac{1-R}{\varepsilon})$. We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from $1-R-\varepsilon$ errors with list size $(1/\varepsilon)^{O(1/\varepsilon)}$. We provide a deterministic list-decoding algorithm for both constructions running in time $O_ε(1)\mathsf{poly}(n)$. In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal $1-R$ radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.

0.54

An Improved Johnson Bound for List-Decoding with Hints

cs.IT ·2026-10-27 ·Swastik Kopparty, Harry Sha
similarity 0.68
Abstract

This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $δ$ is automatically list-decodable with small list size up to a certain radius $J(δ)$ around any received word $r$. We show that if the received word $r$ is known to have some codewords that are somewhat close to it (we call these ``hints"), then $C$ is list-decodable with small list size up to an even larger radius around $r$. We determine the optimal list-decoding radius in this setting for single and multiple hints over both large and small alphabets and show that this radius is the optimum of a natural convex program. Remarkably, even a single hint that is $(J(δ)-ε)$-close to $r$ improves the list-decoding radius around $r$ to $J(δ)+ε'$. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.

0.19