Name
Abstract | ||
|---|---|---|
AbstractWe 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^{ \varepsilon }$ with rate that is exponentially small in $1/ \varepsilon $ . 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/TIT.2020.3023962 | Periodicals |
Keywords | DocType | Volume |
Coding theory, tensor codes, list-decoding and recovery, local codes | Conference | 67 |
Issue | ISSN | Citations |
1 | 0018-9448 | 1 |
PageRank | References | Authors |
0.35 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Nicolas Resch | 2 | 4 | 2.80 |
| Noga Ron-Zewi | 3 | 40 | 9.89 |
| Shubhangi Saraf | 4 | 263 | 24.55 |
| Shashwat Silas | 5 | 2 | 1.40 |