In theoretical computer science, a small-bias sample space (also known as
-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
that is generated by picking a uniform element from a multiset
is the size of the multiset that generates the sample space.
is a function that maps strings of length
The seed length of the generator is the number
-balanced if the Hamming weight of every nonzero codeword
is a linear code, its generator matrix is an
The probabilistic method gives a non-explicit construction that achieves size
[2] The construction is non-explicit in the sense that finding the
However, this non-explicit construction is useful because it shows that these efficient codes exist.
On the other hand, the best known lower bound for the size of
An important application of small-bias sets lies in the construction of almost k-wise independent sample spaces.
is a k-wise independent space if, for all index sets
k-wise independent spaces are fairly well understood.
over the finite field with some prime number
marginals of the distribution are drawn independently and uniformly at random: For each
-almost k-wise independent space if, for all index sets
Naor & Naor (1990) give a general framework for combining small k-wise independent spaces with small
-almost k-wise independent spaces of even smaller size.
be a linear mapping that generates a k-wise independent space and let
That is, when given a uniformly random input, the output of
is a k-wise independent space, and the output of
[3] As mentioned above, Alon, Babai & Itai (1986) construct a generator
-almost k-wise independent space, we need to set
and a sample space of total size