Near-Optimal List-Recovery of Linear Code Families

Abstract

We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independent of the alphabet size and length). That is, over alphabets of size at least ${\ell }^{\hat{I}\text{c◯}(1/\epsilon )}$, random linear codes of rate $R$ are $(1-R-\epsilon ,\ell ,(\ell /\epsilon {)}^{O(\ell /\epsilon )})$-list-recoverable for all $R\in (0,1)$ and $\ell$. Together with a result of Levi, Mosheiff, and Shagrithaya, this implies that randomly punctured Reed-Solomon codes also achieve list-recovery capacity. We also prove that our output list size is near-optimal among all linear codes: all $(1-R-\epsilon ,\ell ,L)$-list-recoverable linear codes must have $L\ge {\ell }^{\hat{I}\text{c◯}(R/\epsilon )}$. Our simple upper bound combines the Zyablov-Pinsker argument with recent bounds from Kopparty, Ron-Zewi, Saraf, Wootters, and Tamo on the maximum intersection of a "list-recovery ball" and a low-dimensional subspace with large distance. Our lower bound is inspired by a recent lower bound of Chen and Zhang.

13 pages