Improved Explicit Near-Optimal Codes in the High-Noise Regimes

Abstract

We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\epsilon }{2}$ fraction of errors and list decodable from $1-\epsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows. 1. Explicit Near-Optimal Linear Time Uniquely Decodable Codes: We construct a family of explicit ${\mathbb{F}}_2$-linear codes with rate $\hat{I}\text{c◯}(\epsilon )$ and alphabet size $2^{\mathrm{poly}\log (1/\epsilon )}$, that are capable of correcting $e$ errors and $s$ erasures whenever $2e+s<(1-\epsilon )n$ in linear-time. 2. Explicit Near-Optimal List Decodable Codes: We construct a family of explicit list decodable codes with rate $\hat{I}\text{c◯}(\epsilon )$ and alphabet size $2^{\mathrm{poly}\log (1/\epsilon )}$, that are capable of list decoding from $1-\epsilon$ fraction of errors with a list size $L=\exp \exp \exp ({\log }^{\ast }n)$ in polynomial time. 3. List Decodable Code with Near-Optimal List Size: We construct a family of explicit list decodable codes with an optimal list size of $O(1/\epsilon )$, albeit with a suboptimal rate of $O({\epsilon }^2)$, capable of list decoding from $1-\epsilon$ fraction of errors in polynomial time. Furthermore, we introduce a new combinatorial object called multi-set disperser, and use it to give a family of list decodable codes with near-optimal rate $\frac{\epsilon }{{\log }^2(1/\epsilon )}$ and list size $\frac{{\log }^2(1/\epsilon )}{\epsilon }$, that can be constructed in probabilistic polynomial time and decoded in deterministic polynomial time. We also introduce new decoding algorithms that may prove valuable for other graph-based codes.

28 pages. To appear in SODA 2025