2025/12/08 by Goyal, Rohan, Guruswami, Venkatesan
Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Computational Complexity (cs.CC) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2512.08017
openalex publication_date 2025/12/08 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
List recovery of error-correcting codes has emerged as a fundamental notion with broad applications across coding theory and theoretical computer science. Folded Reed-Solomon (FRS) and univariate multiplicity codes are explicit constructions which can be efficiently list-recovered up to capacity, namely a fraction of errors approaching 1-R where R is the code rate. Chen and Zhang and related works showed that folded Reed-Solomon codes and linear codes must have list sizes exponential in 1/ε for list-recovering from an error-fraction 1-R-ε. These results suggest that one cannot list-recover FRS codes in time that is also polynomial in 1/ε. In contrast to such limitations, we show, extending algorithmic advances of Ashvinkumar, Habib, and Srivastava for list decoding, that even if the lists in the case of list-recovery are large, they are highly structured. In particular, we can output a compact description of a set of size only ℓO((log ℓ)/ε) which contains the relevant list, while running in time only polynomial in 1/ε (the previously known compact description due to Guruswami and Wang had size ≈ nℓ/ε). We also improve on the state-of-the-art algorithmic results for the task of list-recovery.