Volume 9 (2013) Article 5 pp. 253-272
Constructing Small-Bias Sets from Algebraic-Geometric Codes
Revised: October 29, 2012
Published: February 20, 2013
[PDF (262K)] [PS (980K)] [Source ZIP]
Keywords: small-bias sets, algebraic geometry, AG codes, Goppa codes
ACM Classification: F.2.2, G.2
AMS Classification: 94B27, 12Y05

Abstract: [Plain Text Version]


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.

A preliminary version of this paper appeared in FOCS 2009.