Average-Radius List-Decodability of Random Linear Codes

Venkatesan Guruswami, Shilun Li, Mihir Singhal

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…