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.
Let
X
be a probability distribution over
{
0
,
1
}
n
. The bias of
X
with respect to a set of indices
I
⊆
{
1
,
…
,
n
}
is defined as
bias
I
(
X
)
=
|
Pr
x
∼
X
(
∑
i
∈
I
x
i
=
0
)
−
Pr
x
∼
X
(
∑
i
∈
I
x
i
=
1
)
|
=
|
2
⋅
Pr
x
∼
X
(
∑
i
∈
I
x
i
=
0
)
−
1
|
,
where the sum is taken over
F
2
, the finite field with two elements. In other words, the sum
∑
i
∈
I
x
i
equals
0
if the number of ones in the sample
x
∈
{
0
,
1
}
n
at the positions defined by
I
is even, and otherwise, the sum equals
1
. For
I
=
∅
, the empty sum is defined to be zero, and hence
bias
∅
(
X
)
=
1
.
A probability distribution
X
over
{
0
,
1
}
n
is called an
ϵ
-biased sample space if
bias
I
(
X
)
≤
ϵ
holds for all non-empty subsets
I
⊆
{
1
,
2
,
…
,
n
}
.
An
ϵ
-biased sample space
X
that is generated by picking a uniform element from a multiset
X
⊆
{
0
,
1
}
n
is called
ϵ
-biased set. The size
s
of an
ϵ
-biased set
X
is the size of the multiset that generates the sample space.
An
ϵ
-biased generator
G
:
{
0
,
1
}
ℓ
→
{
0
,
1
}
n
is a function that maps strings of length
ℓ
to strings of length
n
such that the multiset
X
G
=
{
G
(
y
)
|
y
∈
{
0
,
1
}
ℓ
}
is an
ϵ
-biased set. The seed length of the generator is the number
ℓ
and is related to the size of the
ϵ
-biased set
X
G
via the equation
s
=
2
ℓ
.
There is a close connection between
ϵ
-biased sets and
ϵ
-balanced linear error-correcting codes. A linear code
C
:
{
0
,
1
}
n
→
{
0
,
1
}
s
of message length
n
and block length
s
is
ϵ
-balanced if the Hamming weight of every nonzero codeword
C
(
x
)
is between
(
1
2
−
ϵ
)
s
and
(
1
2
+
ϵ
)
s
. Since
C
is a linear code, its generator matrix is an
(
n
×
s
)
-matrix
A
over
F
2
with
C
(
x
)
=
x
⋅
A
.
Then it holds that a multiset
X
⊂
{
0
,
1
}
n
is
ϵ
-biased if and only if the linear code
C
X
, whose columns are exactly elements of
X
, is
ϵ
-balanced.
Usually the goal is to find
ϵ
-biased sets that have a small size
s
relative to the parameters
n
and
ϵ
. This is because a smaller size
s
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.
The probabilistic method gives a non-explicit construction that achieves size
s
=
O
(
n
/
ϵ
2
)
. The construction is non-explicit in the sense that finding the
ϵ
-biased set requires a lot of true randomness, which does not help towards the goal of reducing the overall randomness. 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
ϵ
-biased sets is
s
=
Ω
(
n
/
(
ϵ
2
log
(
1
/
ϵ
)
)
, that is, in order for a set to be
ϵ
-biased, it must be at least that big.
There are many explicit, i.e., deterministic constructions of
ϵ
-biased sets with various parameter settings:
Naor & Naor (1990) achieve
s
=
n
poly
(
ϵ
)
. 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.
Alon et al. (1992) achieve
s
=
O
(
n
ϵ
log
(
n
/
ϵ
)
)
2
. One of their constructions is the concatenation of Reed–Solomon codes with the Hadamard code; this concatenation turns out to be an
ϵ
-balanced code, which gives rise to an
ϵ
-biased sample space via the connection mentioned above.
Concatenating Algebraic geometric codes with the Hadamard code gives an
ϵ
-balanced code with
s
=
O
(
n
ϵ
3
log
(
1
/
ϵ
)
)
.
Ben-Aroya & Ta-Shma (2009) achieves
s
=
O
(
n
ϵ
2
log
(
1
/
ϵ
)
)
5
/
4
.
These bounds are mutually incomparable. In particular, none of these constructions yields the smallest
ϵ
-biased sets for all settings of
ϵ
and
n
.
An important application of small-bias sets lies in the construction of almost k-wise independent sample spaces.
A random variable
Y
over
{
0
,
1
}
n
is a k-wise independent space if, for all index sets
I
⊆
{
1
,
…
,
n
}
of size
k
, the marginal distribution
Y
|
I
is exactly equal to the uniform distribution over
{
0
,
1
}
k
. That is, for all such
I
and all strings
z
∈
{
0
,
1
}
k
, the distribution
Y
satisfies
Pr
Y
(
Y
|
I
=
z
)
=
2
−
k
.
Constructions and bounds
k-wise independent spaces are fairly well-understood.
A simple construction by Joffe (1974) achieves size
n
k
.
Alon, Babai & Itai (1986) construct a k-wise independent space whose size is
n
k
/
2
.
Chor et al. (1985) prove that no k-wise independent space can be significantly smaller than
n
k
/
2
.
Joffe (1974) constructs a
k
-wise independent space
Y
over the finite field with some prime number
n
>
k
of elements, i.e.,
Y
is a distribution over
F
n
n
. The initial
k
marginals of the distribution are drawn independently and uniformly at random:
(
Y
0
,
…
,
Y
k
−
1
)
∼
F
n
k
.
For each
i
with
k
≤
i
<
n
, the marginal distribution of
Y
i
is then defined as
Y
i
=
Y
0
+
Y
1
⋅
i
+
Y
2
⋅
i
2
+
⋯
+
Y
k
−
1
⋅
i
k
−
1
,
where the calculation is done in
F
n
. Joffe (1974) proves that the distribution
Y
constructed in this way is
k
-wise independent as a distribution over
F
n
n
. The distribution
Y
is uniform on its support, and hence, the support of
Y
forms a
k
-wise independent set. It contains all
n
k
strings in
F
n
k
that have been extended to strings of length
n
using the deterministic rule above.
A random variable
Y
over
{
0
,
1
}
n
is a
δ
-almost k-wise independent space if, for all index sets
I
⊆
{
1
,
…
,
n
}
of size
k
, the restricted distribution
Y
|
I
and the uniform distribution
U
k
on
{
0
,
1
}
k
are
δ
-close in 1-norm, i.e.,
∥
Y
|
I
−
U
k
∥
1
≤
δ
.
Naor & Naor (1990) give a general framework for combining small k-wise independent spaces with small
ϵ
-biased spaces to obtain
δ
-almost k-wise independent spaces of even smaller size. In particular, let
G
1
:
{
0
,
1
}
h
→
{
0
,
1
}
n
be a linear mapping that generates a k-wise independent space and let
G
2
:
{
0
,
1
}
ℓ
→
{
0
,
1
}
h
be a generator of an
ϵ
-biased set over
{
0
,
1
}
h
. That is, when given a uniformly random input, the output of
G
1
is a k-wise independent space, and the output of
G
2
is
ϵ
-biased. Then
G
:
{
0
,
1
}
ℓ
→
{
0
,
1
}
n
with
G
(
x
)
=
G
1
(
G
2
(
x
)
)
is a generator of an
δ
-almost
k
-wise independent space, where
δ
=
2
k
/
2
ϵ
.
As mentioned above, Alon, Babai & Itai (1986) construct a generator
G
1
with
h
=
k
2
log
n
, and Naor & Naor (1990) construct a generator
G
2
with
ℓ
=
log
s
=
log
h
+
O
(
log
(
ϵ
−
1
)
)
. Hence, the concatenation
G
of
G
1
and
G
2
has seed length
ℓ
=
log
k
+
log
log
n
+
O
(
log
(
ϵ
−
1
)
)
. In order for
G
to yield a
δ
-almost k-wise independent space, we need to set
ϵ
=
δ
2
−
k
/
2
, which leads to a seed length of
ℓ
=
log
log
n
+
O
(
k
+
log
(
δ
−
1
)
)
and a sample space of total size
2
ℓ
≤
log
n
⋅
poly
(
2
k
⋅
δ
−
1
)
.
