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