List Recovery for Random Low-Rate Linear Codes

Abstract

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $\hat{I}\pm$, and accuracy parameter $\epsilon$, a random $d$-dimensional linear code $C\subseteq {\mathbb{F}}_p^n$ is, with high probability, $(\hat{I}\pm ,\ell ,\frac{1+\epsilon }{1-\hat{I}\pm }\ell )$-list recoverable simultaneously for all input list sizes $\ell \le 2^{O_{\hat{I}\pm ,\epsilon ,d}(n/\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 $(\hat{I}\pm ,\ell ,\frac{1+\epsilon }{1-\hat{I}\pm }\ell )$-list recoverable for feasible list sizes $\ell \ge 2^{\hat{I}{\text{c◯}}_{\hat{I}\pm ,\epsilon }(n)}$. In this sense, our result is nearly optimal.