List Recovery for Random Low-Rate Linear Codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916061697277952 |
|---|---|
| author | Hair, Isaac M Sahai, Amit |
| author_facet | Hair, Isaac M Sahai, Amit |
| contents | We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $α$, and accuracy parameter $\varepsilon$, a random $d$-dimensional linear code $C \subseteq \mathbb{F}_p^n$ is, with high probability, $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable simultaneously for all input list sizes $\ell\le 2^{O_{α, \varepsilon, 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 $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable for feasible list sizes $\ell \geq 2^{Ω_{α, \varepsilon}(n)}$. In this sense, our result is nearly optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_30101 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | List Recovery for Random Low-Rate Linear Codes Hair, Isaac M Sahai, Amit Information Theory We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $α$, and accuracy parameter $\varepsilon$, a random $d$-dimensional linear code $C \subseteq \mathbb{F}_p^n$ is, with high probability, $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable simultaneously for all input list sizes $\ell\le 2^{O_{α, \varepsilon, 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 $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable for feasible list sizes $\ell \geq 2^{Ω_{α, \varepsilon}(n)}$. In this sense, our result is nearly optimal. |
| title | List Recovery for Random Low-Rate Linear Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2605.30101 |