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)
“through the spaces of the dark
Midnight shakes the memory
As a madman shakes a dead geranium.”
—T.S. (Thomas Stearns)