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:
“The present war having so long cut off all communication with Great-Britain, we are not able to make a fair estimate of the state of science in that country. The spirit in which she wages war is the only sample before our eyes, and that does not seem the legitimate offspring either of science or of civilization.”
—Thomas Jefferson (1743–1826)
“Surely, we are provided with senses as well fitted to penetrate the spaces of the real, the substantial, the eternal, as these outward are to penetrate the material universe. Veias, Menu, Zoroaster, Socrates, Christ, Shakespeare, Swedenborg,—these are some of our astronomers.”
—Henry David Thoreau (1817–1862)