首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:A Note on Amplifying the Error-Tolerance of Locally Decodable Codes
  • 本地全文:下载
  • 作者:Avraham Ben-Aroya ; Klim Efremenko ; Amnon Ta-Shma
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2010
  • 卷号:2010
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Trevisan~\cite{Tre03} suggested a transformation that allows amplifying the error rate a code can handle. We observe that this transformation, that was suggested in the non-local setting, works also in the local setting and thus gives a generic, simple way to amplify the error-tolerance of locally decodable codes.
    Specifically, this shows how to transform a locally decodable code that can tolerate a constant fraction of errors
    to a locally decodable code that can recover from a much higher error-rate, and how to transform such locally
    decodable codes to \emph{locally list-decodable codes}.

    The transformation of~\cite{Tre03} involves a simple composition with an \emph{approximately} locally (list) decodable code.
    Using a construction of such codes by Impagliazzo et al.~\cite{IJKW10}, the transformation incurs only a negligible
    growth in the length of the code and in the query complexity.

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