Rui-Qi Zhu

Asymptotically Optimal List Size of Random Linear Codes

We prove that for every fixed prime power $q$, every $p\in(0,1-1/q)$, and every $\varepsilon>0$ with $1-H_q(p)-\varepsilon>0$, a random linear code over $\mathbb{F}_q$ of rate $1-H_q(p)-\varepsilon$ is $(p,\,\left\lceil\frac{H_q(p)}{\varepsilon}\right\rceil+O_{p,q}(1))\text{-list-decodable}$ with probability at least $...