License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.68
URN: urn:nbn:de:0030-drops-112832
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11283/
Kopparty, Swastik ;
Resch, Nicolas ;
Ron-Zewi, Noga ;
Saraf, Shubhangi ;
Silas, Shashwat
On List Recovery of High-Rate Tensor Codes
Abstract
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.
BibTeX - Entry
@InProceedings{kopparty_et_al:LIPIcs:2019:11283,
author = {Swastik Kopparty and Nicolas Resch and Noga Ron-Zewi and Shubhangi Saraf and Shashwat Silas},
title = {{On List Recovery of High-Rate Tensor Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {68:1--68:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11283},
URN = {urn:nbn:de:0030-drops-112832},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.68},
annote = {Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes}
}
|
Keywords: |
|
Coding theory, Tensor codes, List-decoding and recovery, Local codes |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
17.09.2019 |
