Epsilon-Biased Sample Spaces
Encyclopedia
In computer science 
-biased sample spaces, also known as 
-biased generators or small-bias probability spaces, 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
.
be binary random variables and 
be their joint probability distribution. The random variables 
are said to be 
-biased if for all subsets 
,
-biased sample spaces, also known as -biased generators or small-bias probability spaces, 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'sPCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
.
Definition
Let be binary random variables and be their joint probability distribution. The random variables are said to be -biased if for all subsets ,