A (k,\epsilon)-biased sample space is a distribution over \{0,1\}^n that \epsilon-fools every nonempty linear test of size at most k. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.

When ... more >>>