Constructing Small-Bias Sets from Algebraic-Geometric Codes
Avraham Ben-Aroya, Amnon Ta‐Shma · 2009
We give an explicit construction of an ¿-biased set over k bits of size O(k/¿2 log(1/¿))5/4This improves upon previous explicit constructions when e 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 e-biased sets with parameters nearly matching the lower bound, and in particular giving binary error correcting codes beating the Gilbert-Varshamov bound.