2026-09-10T09:44:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27784 2026-09-09T12:19:38Z ddc:004 open_access

Fast List Recovery of Univariate Multiplicity Codes Goyal, Rohan Harsha, Prahladh Kumar, Mrinal Shankar, Ashutosh list-recovery multiplicity-codes near-linear-algorithm Recent work gave near-linear time algorithms for list decoding Folded Reed-Solomon codes and univariate multiplicity codes up to capacity in their natural parameter regimes. Unlike most known list decoding algorithms, these techniques appeared inherently tied to list decoding, and it was unclear whether they could be extended to list recovery in near-linear time. In this work, we resolve this question by giving Õ(n)-time algorithms for list recovery of Folded Reed-Solomon codes and univariate multiplicity codes up to capacity, where n is the block length. Our algorithms build on the lattice-based framework of the prior work, augmented with a new technical ingredient: the construction of suitably structured lattices over the univariate polynomial ring that capture the list recovery problem for these codes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohan Goyal and Prahladh Harsha and Mrinal Kumar and Ashutosh Shankar 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.67 urn:nbn:de:0030-drops-277840 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.67 eng https://creativecommons.org/licenses/by/4.0/legalcode