Shashwat Silas

The list size of random linear codes at capacity

Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of...