On the List-Decodability of Random Linear Codes

Venkatesan Guruswami, Johan Hastad, Swastik Kopparty

For every fixed finite field $\F_q$, $p\in (0,1-1/q)$ and $\epsilon >0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-\epsilon )n$ has the proper…