Epsilon-Biased Sample Spaces

From Wikipedia, the free encyclopedia

In computer science $ε$ -biased sample spaces, also known as $ε$ -biased generators or $ε$ -biased random variables or $ε$ -biased sets, refer to small probability spaces that approximate larger spaces as defined below. Efficient constructions of $ε$ -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.

[edit] 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 $ε$ -biased if for all subsets $S \subseteq \{1,2,\ldots,n\}$ ,