Epsilon-Biased Sample Spaces

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)

    Though there were numerous vessels at this great distance in the horizon on every side, yet the vast spaces between them, like the spaces between the stars,—far as they were distant from us, so were they from one another,—nay, some were twice as far from each other as from us,—impressed us with a sense of the immensity of the ocean, the “unfruitful ocean,” as it has been called, and we could see what proportion man and his works bear to the globe.
    Henry David Thoreau (1817–1862)