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.

# Monthly Archives: May 2014

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

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.