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

CREATORIsaac M Hair * and Amit Sahai †
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32528
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30101

Browse the full library · About the Tower of Babel