Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SMALL-BIAS SAMPLE SPACES:
Reports tagged with small-bias sample spaces:
TR12-050 | 25th April 2012
Avraham Ben-Aroya, Gil Cohen

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.