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-biased sample spaces are equivalent to -balanced error-correcting codes.

Definition

Bias

be a probability distribution. The bias is defined as

, the finite field, the empty sum.

ϵ-biased sample space

is called an -biased sample space.

ϵ-biased set

that is generated by picking a uniform element from a multiset is called -biased set. The size is the size of the multiset that generates the sample space.

ϵ-biased generator

-biased set. The seed length.

Connection with epsilon-balanced error-correcting codes

-biased sets and -balanced linear error-correcting codes of message length and block length is -balanced if the Hamming weight is a linear code, its generator matrix.

-biased if and only if-balanced.

Constructions of small epsilon-biased sets

means that the amount of randomness needed to pick a random element from the set is smaller, and so the set can be used to fool parities using few random bits.

Theoretical bounds

The probabilistic method.-biased, it must be at least that big.

Explicit constructions

-biased sets with various parameter settings:

• . The construction makes use of Justesen codes (which is a concatenation of Reed–Solomon codes with the Wozencraft ensemble) as well as expander walk sampling.

• . One of their constructions is the concatenation of Reed–Solomon codes with the Hadamard code-biased sample space via the connection mentioned above.

• Concatenating Algebraic geometric codes with the Hadamard code.

• .

• which is almost optimal because of the lower bound.

.

Application: almost k-wise independence

An important application of small-bias sets lies in the construction of almost k-wise independent sample spaces.

k-wise independent spaces

is a k-wise independent space, the marginal distribution is exactly equal to the uniform distribution.

Constructions and bounds

k-wise independent spaces are fairly well understood.

• A simple construction by .

• .

• .

Joffe's construction

over the finite field with some prime number marginals of the distribution are drawn independently and uniformly at random:

1. .

is then defined as

. forms a -wise independent set using the deterministic rule above.

Almost k-wise independent spaces

is a -almost k-wise independent space-close in 1-norm.

Constructions

be a linear mapping.

As mentioned above, , and .

Notes

References