2026-08-17T03:44:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24419 2025-12-12T15:01:41Z ddc:004 open_access

Near-Optimal List-Recovery of Linear Code Families Li, Ray Shagrithaya, Nikhil Error-Correcting Codes Randomness List-Recovery Reed-Solomon Codes Random Linear Codes 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 𝓁^Ω(1/ε), random linear codes of rate R are (1-R-ε, 𝓁, (𝓁/ε)^O(𝓁/ε))-list-recoverable for all R ∈ (0,1) and 𝓁. 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-ε, 𝓁, L)-list-recoverable linear codes must have L ≥ 𝓁^{Ω(R/ε)}. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ray Li and Nikhil Shagrithaya 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.53 urn:nbn:de:0030-drops-244199 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.53 eng https://creativecommons.org/licenses/by/4.0/legalcode