List Recovery for Random Low-Rate Linear Codes

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $\alpha$, and accuracy parameter $\epsilon$, a random $d$-dimensional linear code $C\subseteq {\mathbb{F}}_p^n$ is, with high probability, $(\alpha ,\mathrm{\ell },\frac{1+\epsilon }{1-\alpha }\mathrm{\ell })$-list recoverable simultaneously for all input list sizes $\mathrm{\ell }\le 2^{O_{\alpha ,\epsilon ,d}(n\mathrm{/}\log n)}$. The proof is inspired by work of Matoušek, Přívětivý, and Škovroň on reconstructing point sets from their projections. It combines a deterministic graph-theoretic certificate, a nonvanishing determinant criterion, and the Schwartz–Zippel lemma. We also give a lower bound showing that any linear code $C\subseteq {\mathbb{F}}_p^n$ of dimension at least two cannot be $(\alpha ,\mathrm{\ell },\frac{1+\epsilon }{1-\alpha }\mathrm{\ell })$-list recoverable for feasible list sizes $\mathrm{\ell }\ge 2^{{\mathrm{\Omega }}_{\alpha ,\epsilon }(n)}$. In this sense, our result is nearly optimal.