List recovery for random low-rate linear codes
Isaac M Hair * and Amit Sahai † · 2026
Read List recovery for random low-rate linear codes by Isaac M Hair * and Amit Sahai † (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30101.txt.
Description
Isaac M Hair and Amit Sahai establish list recovery for random low-rate linear codes over large prime fields. For fixed dimension, error share and accuracy target, a random code is list recoverable for all list sizes up to an exponentially growing bound. The proof blends a graph certificate, a nonvanishing determinant test and the Schwartz-Zippel lemma. A matching lower bound shows codes of dimension at least two cannot do better for large feasible lists. The result is thus nearly optimal.
Catalog record
| CREATOR | Isaac M Hair * and Amit Sahai † |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32528 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.30101