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

文章基本信息

  • 标题:Constructing Small-Bias Sets from Algebraic-Geometric Codes
  • 本地全文:下载
  • 作者:Avraham Ben-Aroya ; Amnon Ta-Shma
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2013
  • 卷号:9
  • 页码:253-272
  • 出版社:University of Chicago
  • 摘要:

    We give an explicit construction of an $\eps$-biased set over $k$ bits of size $O\left(\frac{k}{\eps^2 \log(1/\eps)}\right)^{5/4}$. This improves upon previous explicit constructions when $\eps$ is roughly (ignoring logarithmic factors) in the range $[k^{-1.5},k^{-0.5}]$. The construction builds on an algebraic geometric code. However, unlike previous constructions, we use low-degree divisors whose degree is significantly smaller than the genus.

  • 关键词:small-bias sets; algebraic geometry; AG codes; Goppa codes
国家哲学社会科学文献中心版权所有