1 Answers
In theoretical computer science, a small-bias sample 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.