Volume 9 (2013)
Article 5 pp. 253-272

Constructing Small-Bias Sets from Algebraic-Geometric Codes

Received: February 21, 2011

Revised: October 29, 2012

Published: February 20, 2013

Revised: October 29, 2012

Published: February 20, 2013

**Keywords:**small-bias sets, algebraic geometry, AG codes, Goppa codes

**Categories:**error-correcting codes, explicit construction, small-bias distribution, algebraic geometry, algebraic-geometric codes, Goppa codes

**ACM Classification:**F.2.2, G.2

**AMS Classification:**94B27, 12Y05

**Abstract:**
[Plain Text Version]

$
\newcommand{\half}{\frac{1}{2}}
\newcommand{\eps}{\epsilon}
\newcommand{\logeps}{\log({1 \over \epsilon})}
\newcommand{\logepsk}{\log({k \over \epsilon})}
\newcommand{\set}[1]{{\left\{#1\right\}}}
\newcommand{\logepsksquare}{\log^2({k \over \epsilon})}
$

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.