Time- and Space-Efficient List Decoding up to Capacity

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)\le \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.