# Some Elementary Constructions of Small-Bias Spaces, Part 2

In this short post, we examine the use of the “randomness” of quadratic characters in constructing small-bias spaces. Specifically, we’ll look at another one of AGHP’s constructions making use of Weil’s character sum estimate as well as a generalization of this argument to $\epsilon$-biased sets over $\mathbb{Z}^n_d$, due to Azar/Motwani/Naor.

# Some Elementary Constructions of Small-Bias Spaces, Part 1

A small-bias space is a distribution over the Boolean hypercube $\{0,1\}^n$ which fools parity tests. Since they were first introduced by Naor/Naor, these objects have been of central importance to the study of pseudorandomness and have found applications in constructing pseudorandom generator fooling small-width branching programs, derandomizing certain algorithms, constructing $(k,\epsilon)$-independent hash functions, and obtaining short PCPs.

In this post we examine four constructions, including an extremely simple construction over $\mathbb{Z}^n_p$ by Alon/Mansour (2002) which generalizes one due to Alon/Goldreich/Hastad/Peralta (1992), another construction based on linear feedback shift registers due to AGHP, and Naor/Naor’s original construction (1990) based on $k$-wise independence (or alternatively Justesen codes) and random walks on expander graphs.