List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding

Abstract

Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power $q$ and $p\in (0,1-1/q)$, random linear codes of rate $1-h_q(p)-\epsilon$ have list size $\frac{h_q(p)}{\epsilon }\cdot (1+o(1))$ as $\epsilon \to 0$, both for list decoding and average-radius list decoding. The conjecture was known for $q=2$ and remained open for larger alphabets. We prove the conjecture for list decoding for every prime power $q$, with the sharper bound $L=\frac{h_q(p)}{\epsilon }+O_{p,q}(1).$ In contrast, we disprove the conjecture for average-radius list decoding. We show that the required list-size leading constant is at least $p\left(1+{\log }_q\frac{(q-1)(1-p)}{p}\right)$, which is strictly larger than $h_q(p)$ whenever $q^p(1-p)>1$. Moreover, for $p=1-\lambda /q$ with fixed $\lambda >1$, the required leading constant can be as large as $\left(\frac{\log \lambda }{e\lambda }+o_q(1)\right)\frac{q}{\log q}.$

arXiv comment32 pages