Skip to content
Preprint

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

Oct 2026 · 0 citations · 43 references
Computer Science Mathematics

TL;DR

It is shown that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size with fixed list size.

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

View source

Similar papers

Preprint Sep 2026

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

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 $\delta=0.1$, our achievable rate increases from $0.162009$ to $0.194890$,...

Han Mao Kiah, Heng-Jia Wei, Rui-Xiao Zeng · 2 citations
Sep 2026

Constant-List Insertion-Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound

We study codes correcting adversarial insertions and deletions with list size $L$ fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size $q\ge2$, retaining explicit dependence on $L$. We establish a combinatorial reduction that t...

Han Mao Kiah, Heng-Jia Wei, Rui-Xiao Zeng · 0 citations
Preprint Oct 2026

An Improved Johnson Bound for List-Decoding with Hints

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

S. Kopparty, Harry Sha · 0 citations
Sep 2026

A New Upper Bound on the Binary Deletion Channel Capacity

We prove that the capacity of the binary deletion channel satisfies $C(d)\le (1-d)/4$ for every $13/20\le d<1$. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added...

Özgür Soysal · 1 citation
Preprint Nov 2026

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at mo...

Ryan Gabrys, Shubhransh Singhvi, E. Yaakobi · 0 citations
Preprint Oct 2026

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

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

Ben-Cheng Fan, M. Kuijper, Jing-Ge Zhu · 1 citation · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.