首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Tensor Products of Weakly Smooth Codes are Robust
  • 本地全文:下载
  • 作者:Eli Ben-Sasson ; Michael Viderman
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2009
  • 卷号:5
  • 出版社:University of Chicago
  • 摘要:

    We continue the study of robust tensor codes and expand the class of base codes that can be used as a starting point for the construction of locally testable codes via robust two-wise tensor products. In particular, we show that all unique-neighbor expander codes and all locally correctable codes, when tensored with any other good-distance code, are robust and hence can be used to construct locally testable codes. Previous works by Dinur et al. 2006 required stronger expansion properties to obtain locally testable codes.

    Our proofs follow by defining the notion of weakly smooth codes that generalize the smooth codes of Dinur et al. We show that weakly smooth codes are sufficient for constructing robust tensor codes. Using the weaker definition, we are able to expand the family of base codes to include the aforementioned ones.

  • 关键词:linear code, tensor code, expander code
国家哲学社会科学文献中心版权所有