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.

Continue reading


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.

Continue reading