Theory of Computing
-------------------
Title : Constructing Small-Bias Sets from Algebraic-Geometric Codes
Authors : Avraham Ben-Aroya and Amnon Ta-Shma
Volume : 9
Number : 5
Pages : 253-272
URL : https://theoryofcomputing.org/articles/v009a005
Abstract
--------
We give an explicit construction of an $\epsilon$-biased set over
$k$ bits of size $O(k/(\epsilon^2 \log(1/\epsilon))^{5/4}$. This
improves upon previous explicit constructions when $\epsilon$ 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.
A preliminary version of this paper appeared in FOCS 2009.