首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Local List Recovery of High-rate Tensor Codes & Applications
  • 本地全文:下载
  • 作者:Brett Hemenway ; Noga Ron-Zewi ; Mary Wootters
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first {\em capacity-achieving} locally list-decodable codes (over constant-sized alphabet); the first {\em capacity achieving} globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known.

    Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes. We show that tensor powers of (globally) list-recoverable codes are `approximately' locally list-recoverable, and that the `approximately' modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions of high-rate globally list-recoverable codes and high-rate locally decodable codes finishes the construction.

国家哲学社会科学文献中心版权所有