Epsilon-Biased Sample Spaces

In computer science $epsilon$-biased sample spaces, also known as $epsilon$-biased generators or $epsilon$-biased random variables or $epsilon$-biased sets, refer to small probability spaces that approximate larger spaces as defined below. Efficient constructions of $epsilon$-biased sample spaces have found many applications in computer science, some of which are - derandomization of algorithms, construction of error-correcting codes, and construction of PCP's.

Definition

Let $X\_\{1\},\; X\_\{2\},\; ldots,\; X\_\{n\}$ be binary random variables and $D$ be their joint probability distribution. The random variables $X\_\{1\},\; X\_\{2\},\; ldots,\; X\_\{n\}$ are said to be $epsilon$-biased if for all subsets $S\; subseteq\; \{1,2,ldots,n\}$ ,

References

* [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias_abs.html Gives efficient construction of $epsilon$-biased spaces]
* [http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l07.ps Introduction from a course by Oded Goldreich]
* [http://www.cs.utexas.edu/~diz/395T/01/lec7.ps Brief description of a construction and an application to constructing almost k-wise independent spaces]