首页    期刊浏览 2025年02月22日 星期六
登录注册

文章基本信息

  • 标题:On List Recovery of High-Rate Tensor Codes
  • 本地全文:下载
  • 作者:Swastik Kopparty ; Nicolas Resch ; Noga Ron-Zewi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-39
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 {\em approximately} locally list recoverable, as well as globally list recoverable in {\em 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) {\em probabilistic} near-linear time global list decoding algorithms. This was also yielded constant-rate codes approaching the Gilbert-Varshamov bound with {\em 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 {\em deterministic} near-linear time. This yields in turn the first capacity-achieving list decodable codes with {\em deterministic} near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert Varshamov bound with {\em 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 constant-rate codes approaching the Gilbert-Varshamov bound that are {\em 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 with rate that is exponentially small in 1 .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 (1 log log N ) on the product of query complexity and output list size for locally list recovering high-rate tensor codes.

  • 关键词:Gilbert--Varshamov bound ; List Decodable Codes ; List Recovery ; Locally correctable codes ; Tensor codes
国家哲学社会科学文献中心版权所有