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 -biased sets over , due to Azar/Motwani/Naor.
A small-bias space is a distribution over the Boolean hypercube 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 -independent hash functions, and obtaining short PCPs.
In this post we examine four constructions, including an extremely simple construction over 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 -wise independence (or alternatively Justesen codes) and random walks on expander graphs.