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

文章基本信息

  • 标题:Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
  • 本地全文:下载
  • 作者:Venkatesan Guruswami ; Madhu Sudan ; Ameya Velingker
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length N and distance d is known to be testable with O(Nd) queries, and has a dimension of N−(logN)logd. The polylogarithmically small co-dimension is the basis of constructions of small set expanders with many ``bad'' eigenvalues, and size-efficient PCPs based on a shorter version of the long code. The smallest possible co-dimension for a distance d code (without any testability requirement) is 2dlogN, achieved by BCH codes. This raises the natural question of understanding where in the spectrum between the two classical families, Reed-Muller and BCH, the optimal co-dimension of a distance d LTC lies --- in other words the ``price'' one has to pay for local testability.

  • 关键词:Algebraic coding theory; derandomization; Locally testable codes; lower bounds; Property Testing; Reed-Muller codes; small set expander
国家哲学社会科学文献中心版权所有