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

文章基本信息

  • 标题:Subspace Evasive Sets
  • 本地全文:下载
  • 作者:Zeev Dvir ; Shachar Lovett
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2011
  • 卷号:2011
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) who showed how such constructions over the binary field can be used to construct explicit Ramsey graphs. More recently, Guruswami (2011) showed that, over large finite fields (of size polynomial in n), subspace evasive sets can be used to obtain explicit list-decodable codes with optimal rate and constant list-size. In this work we construct subspace evasive sets over large fields and use them to reduce the list size of folded Reed-Solomon codes form poly(n) to a constant.

  • 关键词:Affine extractors; folded reed-solomon codes; list-decoding
国家哲学社会科学文献中心版权所有