Near-Optimal List-Recovery of Linear Code Families
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916634841579520 |
|---|---|
| author | Li, Ray Shagrithaya, Nikhil |
| author_facet | Li, Ray Shagrithaya, Nikhil |
| contents | 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^{Ω(1/\varepsilon)}$, random linear codes of rate $R$ are $(1-R-\varepsilon, \ell, (\ell/\varepsilon)^{O(\ell/\varepsilon)})$-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-\varepsilon, \ell, L)$-list-recoverable linear codes must have $L\ge \ell^{Ω(R/\varepsilon)}$.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13877 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal List-Recovery of Linear Code Families Li, Ray Shagrithaya, Nikhil Information Theory Combinatorics 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^{Ω(1/\varepsilon)}$, random linear codes of rate $R$ are $(1-R-\varepsilon, \ell, (\ell/\varepsilon)^{O(\ell/\varepsilon)})$-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-\varepsilon, \ell, L)$-list-recoverable linear codes must have $L\ge \ell^{Ω(R/\varepsilon)}$. 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. |
| title | Near-Optimal List-Recovery of Linear Code Families |
| topic | Information Theory Combinatorics |
| url | https://arxiv.org/abs/2502.13877 |