CS Paper Radar

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

Neehar Verma, Camilla Hollanti, Razane Tajeddine

cs.IT math.CO ·submitted 2026-10-16 10:41 UTC · v1
theory

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$.

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.76
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

Insdel Decoding Algorithms for Maximum Distance Separable Codes

cs.IT ·2026-10-25 ·Bencheng Fan, Margreta Kuijper, Jingge Zhu
similarity 0.74
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.

0.19

On the Average List Size of VT Codes under Two Insertions or Two Deletions

cs.IT ·2026-10-11 ·Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, Eitan Yaakobi
theory similarity 0.72
Abstract · Submitted to ITW 2027

Levenshtein's classical theorem shows that any code that can uniquely decode from \(t\) deletions can also uniquely decode from \(t\) insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code \(\mathcal{C}\) of length \(n\) that uniquely corrects \(t'\) insertions (or deletions), we are interested in the average number of codewords returned by a \(t\)-insertion (or deletion) list decoder, where \(t' < t\). Focusing on the case of \(t'=1\) and \(t=2\), we find that under two insertions, this quantity is at most \((n+12)/4\) for any VT code of length \(n\), whereas under two deletions it is at least \(n/2 - 10\) when averaged over all length-\(n\) VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.

0.22

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

cs.IT cs.DSmath.CO ·2026-09-04 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.70
Abstract

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

0.35

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.70
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

Time- and Space-Efficient List Decoding up to Capacity

cs.IT cs.CC ·2026-08-16 ·Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters
similarity 0.70
Abstract

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq Σ^N$ and a received word $y \in Σ^N$, find all codewords $c \in C$ so that $δ(c,y) \leq ρ$, where $δ$ is relative Hamming distance and $ρ\in (0,1)$. Codes that approach the optimal trade-off between the rate $R := \log_{|Σ|}(|C|) / N$ and the list-decoding radius $ρ$ are said to achieve capacity.By now, there are constructions of capacity-achieving list-decodable codes with fast near-linear-time list-decoding algorithms, but most existing work has not considered space complexity. In a recent line of work, Cook and Moshkovitz (2024, 2025, 2026) initiated the study of low-space deterministic algorithms for error correcting codes. In particular, in their 2026 paper, they gave a construction of list-decodable codes with deterministic near-linear-time and sublinear space list-decoding algorithms. However, these codes were far from achieving capacity. In this paper, we present list-decodable codes approaching capacity with deterministic time- and space-efficient list-decoding algorithms. More precisely, for any $R \in (0,1)$ and any arbitrarily small constant $τ> 0$, we present a family of codes $C\subseteq Σ^N$ with rate $R$ that are deterministically list-decodable up to radius $ρ= 1 - R - τ$, in time $N^{1 + τ}$ and space $N^τ$ with constant output list size and constant alphabet size. Our results can be extended to capacity-achieving list-recoverable codes.

0.04

Exponentially Larger Deletion-Correcting Codes and Constant-List-Decodable Insertion-Deletion Codes

cs.IT ·2026-09-18 ·Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
theory similarity 0.69
Abstract · 46 pages, 7 figures

We establish improved asymptotic rate bounds for adversarial insertion--deletion codes. For binary unique-deletion correction in the linear-deletion regime, we strictly improve Levenshtein's classical lower-bound expression. At deletion fraction $δ=0.1$, our achievable rate increases from $0.162009$ to $0.194890$, a relative gain of approximately $20.30\%$. For list decoding with any prescribed finite list size $L$, we obtain new achievable-rate bounds for binary deletion and insertion codes. Our approach combines the Lovász local lemma with refined counting of common subsequences and supersequences, using generating functions and run-restricted sampling. We also establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget without changing the code or increasing the list size. It transfers insertion lower bounds at $γ+Lδ$ and deletion upper bounds at $δ+γ/L$ to mixed errors. We also derive a run-counting Levenshtein-type list-decoding upper bound and a higher-order Elias-type upper bound. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion upper bound for every fixed $L$ and $0<γ<q-1$. Numerical comparisons quantify the gains and the remaining gaps.

0.41

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.69
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