Optimal $\varepsilon$-Biased Sets with Just a Little Randomness
Cristopher Moore, Alexander C. Russell · SIAM Journal on Discrete Mathematics · 2015
Subsets of $\mathbb{F}_2^n$ that are $\varepsilon$-biased, meaning that the parity of any set of bits is even or odd with probability $\varepsilon$ close to $1/2$, are powerful tools for derandomization. A simple randomized construction shows that such sets exist of size $O(n/\varepsilon^2)$, and known deterministic constructions achieve sets of size $O(n/\varepsilon^3)$, $O(n^2/\varepsilon^2)$, and $O((n/\varepsilon^2)^{5/4})$. Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size $O(n/\varepsilon^2)$ with as few random bits as possible. Equivalently, we construct small ensembles of error-correcting codes, most of which meet the Gilbert--Varshamov bound. The naive randomized construction requires $O(n^2/\varepsilon^2)$ random bits. We give two constructions. The first uses Nisan's space-bounded pseudorandom generator to partly derandomize the classic Wozencraft ensemble of error-correcting codes and requires $O(n \log (1/\varepsilon))$ bits. Our second construction requires $O(n \log (n/\varepsilon))$ bits; it adds randomness to a Legendre symbol construction of Alon, Goldreich, H\aastad, and Peralta and uses Weil sums to bound high moments of the bias.