Epsilon-Biased Sample Spaces
In theoretical computer science, a small-bias sample space (also known as -biased sample space, -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 -biased sample spaces are equivalent to -balanced error-correcting codes.
Read more about Epsilon-Biased Sample Spaces: Connection With Epsilon-balanced Error-correcting Codes, Constructions of Small Epsilon-biased Sets, Application: Almost K-wise Independence
Famous quotes containing the words sample and/or spaces:
“All that a city will ever allow you is an angle on it—an oblique, indirect sample of what it contains, or what passes through it; a point of view.”
—Peter Conrad (b. 1948)
“Deep down, the US, with its space, its technological refinement, its bluff good conscience, even in those spaces which it opens up for simulation, is the only remaining primitive society.”
—Jean Baudrillard (b. 1929)