首页    期刊浏览 2024年07月16日 星期二
登录注册

文章基本信息

  • 标题:Quasilinear time list-decodable codes for space bounded channels
  • 本地全文:下载
  • 作者:Ronen Shaltiel ; Swastik Kopparty ; Jad Silbak
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-60
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword.Guruswami and Smith, and later work by Shaltiel and Silbak (RANDOM 2016), gave constructions of list-decodable codes with rate approaching 1 − H ( p ) against channels with space s = c log n , with encoding/decoding time \poly ( 2 s ) = \poly ( n c ) .In this paper we show that for every constant 0 p 0 , there are codes with rate R 1 − H ( p ) − , list size \poly (1 ) , and furthermore: \begin{itemize} \item Our codes can handle channels with space s = n (1) , which is much larger than O ( log n ) achieved by previous work. \item We give encoding and decoding algorithms that run in time n \polylog ( n ) . Previous work achieved large and unspecified \poly ( n ) time (even for space s = 1 log n channels). \item We can handle space bounded channels that read the codeword in any order, whereas previous work considered channels that read the codeword in the standard order. \end{itemize} Our construction builds on the machinery of Guruswami and Smith (with some key modifications) replacing some nonconstructive codes and pseudorandom objects (that are found in exponential time by brute force) with efficient explicit constructions. For this purpose we exploit recent results of Haramaty, Lee and Viola (SICOMP 2018) on pseudorandom properties of `` t -wise independence + low weight noise'' which we quantitatively improve using techniques by Forbes and Kelly (FOCS 2018).To make use of such distributions, we give new explicit constructions of binary linear codes that have dual distance of n (1) , and are also polynomial time list-decodable from relative distance \half − , with list size \poly (1 ) . To the best of our knowledge, no such construction was previously known.Somewhat surprisingly, we show that Reed-Solomon codes with dimension k n , have this property if interpreted as binary codes (in some specific interpretation) which we term: ``Raw Reed-Solomon Codes''. A key idea is viewing Reed-Solomon codes as ``bundles'' of certain dual-BCH codewords.

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