Skip to content
Preprint

Time- and Space-Efficient List Decoding up to Capacity

Aug 2026 · 0 citations
Computer Science Mathematics

TL;DR

A family of codes with rate R that are deterministically list-decodable up to radius $\rho = 1 - R - \tau$ in time $N^{1 + \tau}$ and space $N^{\tau}$ with constant output list size and constant alphabet size is presented.

Abstract

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq \Sigma^N$ and a received word $y \in \Sigma^N$, find all codewords $c \in C$ so that $\delta(c,y) \leq \rho$, where $\delta$ is relative Hamming distance and $\rho \in (0,1)$. Codes that approach the optimal trade-off between the rate $R := \log_{|\Sigma|}(|C|) / N$ and the list-decoding radius $\rho$ 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 $\tau>0$, we present a family of codes $C\subseteq \Sigma^N$ with rate $R$ that are deterministically list-decodable up to radius $\rho = 1 - R - \tau$, in time $N^{1 + \tau}$ and space $N^{\tau}$ with constant output list size and constant alphabet size. Our results can be extended to capacity-achieving list-recoverable codes.

View source

Similar papers

Preprint Sep 2026

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

We give a unified hidden-derivative framework for list decoding and mutual correlated agreement of ordinary Reed--Solomon codes over prime fields, on arbitrary prescribed evaluation sets. For every fixed slack $\gamma>0$, every sufficiently large block length $n$, every prime $q\ge n$, and every dimension $1\le k\le(1-...

F. G. Jeronimo · 5 citations · ⚡3
Sep 2026

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

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

Da-Qing Wan, Jun Zhang · 0 citations
Preprint Sep 2026

The list size of random linear codes at capacity

Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of...

Shashwat Silas · 5 citations
Preprint Oct 2026

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

We show that for any $R,\epsilon>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_\epsilon(1)$, and normalized distance at least $\delta_{\mathrm{GV}}(p,R)-\epsilon$. Here, $\delta_{\mathrm{GV}}(p,R)$ denotes the quantum...

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani et al. · 2 citations · ⚡1
Preprint Oct 2026

Logical-Space Theory of Ordered-Statistics Decoding for Quantum LDPC Codes

A framework guides OSD list construction and compression by identifying coverage requirements and distinguishing coverage losses from failures of representative selection, and separating absent-class from wrong-selection failures.

Yun Shang · 0 citations
Preprint Sep 2026

List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding

Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power $q$ and $p\in(0,1-1/q)$, random linear codes of rate $1-h_q(p)-\varepsilon$ have list size $\frac{h_q(p)}{\varepsilon}\cdot(1+o(1))$ as $\varepsilon\to0$, both for list decoding and average-radius list decoding. The conject...

Chen Yuan, Rui-Qi Zhu · 3 citations

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