An [n,k] binary code is eps-balanced if all non-zero codewords are almost
balanced, i.e., have weight at least (1/2-eps)n and at most (1/2+eps)n.
An equivalent notion is that of a small-bias set. We give an explicit
construction of an eps-balanced [n,k] binary code that has length roughly
O(k/eps2)^{5/4}. This improves upon previous explicit constructions when
eps is in the range [k^{-1.5},k^{-0.5}]. The construction builds on an
algebraic-geometric code. Unlike previous constructions, we use low-degree
divisors whose degree is significantly smaller than the genus.
Following our work Felipe Voloch used a variant of Castelnuovo's bound to
show our approach cannot lead to error correcting codes approaching the
Gilbert-Varshamov bound. We show that a careful analysis of Voloch's
argument imply that all dimension k, eps-balanced codes built using our
approach must have length n=Omega(k/eps^{2.5}).
Joint work with Avraham Ben-Aroya. A preliminary version of this paper
appeared in FOCS 2009.
Copyright. All Rights Reserved.