Constructing Small-Bias Sets from Algebraic-Geometric Codes
Constructing Small-Bias Sets from Algebraic-Geometric Codes
复制标题
从代数几何代码构造小偏差集
DOI：
10.4086/toc.2013.v009a005
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Avraham Ben;A. Ta
给出了大小为$O(FRAC{k}{\EPS^2\log(1/\EPS)})^{5/4}$k$位上$\EPS$-偏集的一个显式构造.当$\EPS$大致(忽略对数因子)在$[k^{-1.5}，k^{-0.5}]$范围内时，这改进了以前的显式构造。这种结构建立在代数几何码的基础上。然而，与以前的构造不同的是，我们使用的是次数明显小于亏格的低次因子。研究我们技术的局限性，我们得到一个假设：如果为真，则意味着存在参数接近下界的$\EPS$-偏向集，并且特别地，给出了超越Gilbert-Varshamov界的二进制纠错码。
We give an explicit construction of an $\eps$-biased set over $k$ bits of size $O(\frac{k}{\eps^2 \log(1/\eps)})^{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. Studying the limits of our technique, we arrive at a hypothesis that if true implies the existence of $\eps$-biased sets with parameters nearly matching the lower bound, and in particular giving binary error correcting codes beating the Gilbert-Varshamov bound.