2026-07-23T06:31:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11283 2024-03-06T10:47:53Z ddc:004 open_access

On List Recovery of High-Rate Tensor Codes Kopparty, Swastik Resch, Nicolas Ron-Zewi, Noga Saraf, Shubhangi Silas, Shashwat Coding theory Tensor codes List-decoding and recovery Local codes We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time N^{o(1)}. This improves over prior work by Gopi et. al. (SODA'17; IEEE Transactions on Information Theory'18) that only gave query complexity N^{epsilon} with rate that is exponentially small in 1/epsilon. 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of N^{Omega(1/log log N)} on the product of query complexity and output list size for locally list recovering high-rate tensor codes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Swastik Kopparty and Nicolas Resch and Noga Ron-Zewi and Shubhangi Saraf and Shashwat Silas 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.68 urn:nbn:de:0030-drops-112832 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.68 eng https://creativecommons.org/licenses/by/3.0/legalcode