Average-Radius List-Decodability of Random Linear Codes

Abstract

We prove that for every prime power $q$ and every $p\in (0,1-1/q)$, a random ${\mathbb{F}}_q$-linear code of rate $1-h_q(p)-\epsilon$ is $(p,C_{p,q}/\epsilon )$-average-radius list-decodable with probability at least $1-q^{-\Omega (n)}$, i.e., for every center $y\in {\mathbb{F}}_q^n$, the $C_{p,q}/\epsilon$ codewords closest to $y$ have average fractional Hamming distance at least $p$ from $y$. This extends a similar result for (standard) list-decoding due to Guruswami, Håstad, and Kopparty (2010) to the stronger average-radius guarantee, with the same $O(1/\epsilon )$ list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).