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

文章基本信息

  • 标题:New affine-invariant codes from lifting
  • 本地全文:下载
  • 作者:Alan Guo ; Madhu Sudan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work we explore error-correcting codes derived fromthe ``lifting'' of ``affine-invariant'' codes.Affine-invariant codes are simply linear codes whose coordinatesare a vector space over a field and which are invariant underaffine-transformations of the coordinate space. Lifting takes codesdefined over a vector space of small dimension and lifts them to higherdimensions by requiring their restriction to every subspace ofthe original dimension to be a codeword of the code being lifted.While the operation is of interest on its own, this work focusseson new ranges of parameters that can be obtained by such codes,in the context of local correction and testing.In particular we present four interesting ranges of parameters thatcan be achieved by such lifts, all of which are new in the contextof affine-invariance and some may be new even in general.The main highlight is a construction of high-rate codeswith sublinear time decoding. The only prior construction of suchcodes is due to Kopparty, Saraf and Yekhanin~\cite{KSY}.All our codes are extremely simple, being just lifts of variousparity check codes (codes with one symbol of redundancy), andin the final case, the lift of a Reed-Solomon code.

  • 关键词:Affine-invariance; Lifting; Locally decodable codes; Locally testable codes
国家哲学社会科学文献中心版权所有