Small-bias sample space

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2020) (Learn how and when to remove this message)

In theoretical computer science, a small-bias sample space (also known as ${\displaystyle \epsilon }$-biased sample space, ${\displaystyle \epsilon }$-biased generator, or small-bias probability space) is a probability distribution that fools parity functions. In other words, no parity function can distinguish between a small-bias sample space and the uniform distribution with high probability, and hence, small-bias sample spaces naturally give rise to pseudorandom generators for parity functions.

The main useful property of small-bias sample spaces is that they need far fewer truly random bits than the uniform distribution to fool parities. Efficient constructions of small-bias sample spaces have found many applications in computer science, some of which are derandomization, error-correcting codes, and probabilistically checkable proofs. The connection with error-correcting codes is in fact very strong since ${\displaystyle \epsilon }$-biased sample spaces are equivalent to ${\displaystyle \epsilon }$-balanced error-correcting codes.