Epsilon-Biased Sample Spaces

In computer science $\epsilon$-biased sample spaces, also known as $\epsilon$-biased generators or small-bias probability spaces, 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\}$ ,

$\|Pr_{D}[\sum_{i \in S}X_{i} = 0] - Pr_{D}[\sum_{i \in S}X_{i} = 1]\| < \epsilon .$

References

• Gives efficient construction of $\epsilon$-biased spaces
• Introduction from a course by Oded Goldreich
• Brief description of a construction and an application to constructing almost k-wise independent spaces