Small-bias sample space

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.

Definition

Bias

Let $X$ be a probability distribution over $\{0,1{\}}^n$. The bias of $X$ with respect to a set of indices $I\subseteq \{1,\dots ,n\}$ is defined as

${\text{bias}}_I(X)=|\underset{x\sim X}{\mathrm{Pr}}(\sum _{i\in I}{x}_i=0)-\underset{x\sim X}{\mathrm{Pr}}(\sum _{i\in I}{x}_i=1)|=|2\cdot \underset{x\sim X}{\mathrm{Pr}}(\sum _{i\in I}{x}_i=0)-1|,$

where the sum is taken over ${\mathbb{𝔽}}_2$, the finite field with two elements. In other words, the sum $\sum _{i\in I}{x}_i$ equals $0$ if the number of ones in the sample $x\in \{0,1{\}}^n$ at the positions defined by $I$ is even, and otherwise, the sum equals $1$. For $I=\mathrm{\varnothing }$, the empty sum is defined to be zero, and hence ${\text{bias}}_{\mathrm{\varnothing }}(X)=1$.

ϵ-biased sample space

A probability distribution $X$ over $\{0,1{\}}^n$ is called an $ϵ$-biased sample space if ${\text{bias}}_I(X)\le ϵ$ holds for all non-empty subsets $I\subseteq \{1,2,\dots ,n\}$.

ϵ-biased set

An $ϵ$-biased sample space $X$ that is generated by picking a uniform element from a multiset $X\subseteq \{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.

ϵ-biased generator

An $ϵ$-biased generator $G:\{0,1{\}}^{\ell }\to \{0,1{\}}^n$ is a function that maps strings of length $\ell$ to strings of length $n$ such that the multiset $X_G=\{G(y)|y\in \{0,1{\}}^{\ell }\}$ is an $ϵ$-biased set. The seed length of the generator is the number $\ell$ and is related to the size of the $ϵ$-biased set $X_G$ via the equation $s=2^{\ell }$.

Connection with epsilon-balanced error-correcting codes

There is a close connection between $ϵ$-biased sets and $ϵ$-balanced linear error-correcting codes. A linear code $C:\{0,1{\}}^n\to \{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 $(\frac{1}{2}-ϵ)s$ and $(\frac{1}{2}+ϵ)s$. Since $C$ is a linear code, its generator matrix is an $(n\times s)$-matrix $A$ over ${\mathbb{𝔽}}_2$ with $C(x)=x\cdot A$.

Then it holds that a multiset $X\subset \{0,1{\}}^n$ is $ϵ$-biased if and only if the linear code $C_X$, whose columns are exactly elements of $X$, is $ϵ$-balanced.

Constructions of small epsilon-biased sets

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.

Theoretical bounds

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=\mathrm{\Omega }(n/({ϵ}^2\log (1/ϵ))$, that is, in order for a set to be $ϵ$-biased, it must be at least that big.

Explicit constructions

There are many explicit, i.e., deterministic constructions of $ϵ$-biased sets with various parameter settings:

• (Naor Naor) achieve $s=\frac{n}{\text{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 Goldreich) achieve $s=O{\left(\frac{n}{ϵ\log (n/ϵ)}\right)}^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\left(\frac{n}{{ϵ}^3\log (1/ϵ)}\right)$.
• (Ben-Aroya Ta-Shma) achieves $s=O{\left(\frac{n}{{ϵ}^2\log (1/ϵ)}\right)}^{5/4}$.
• (Ta-Shma 2017) achieves $s=O\left(\frac{n}{{ϵ}^{2+o(1)}}\right)$ which is almost optimal because of the lower bound.

These bounds are mutually incomparable. In particular, none of these constructions yields the smallest $ϵ$-biased sets for all settings of $ϵ$ and $n$.

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

A random variable $Y$ over $\{0,1{\}}^n$ is a k-wise independent space if, for all index sets $I\subseteq \{1,\dots ,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\in \{0,1{\}}^k$, the distribution $Y$ satisfies $\underset{Y}{\mathrm{Pr}}(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) construct a k-wise independent space whose size is $n^{k/2}$.
• (Chor Goldreich) prove that no k-wise independent space can be significantly smaller than $n^{k/2}$.

Joffe's construction

(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 ${\mathbb{𝔽}}_n^n$. The initial $k$ marginals of the distribution are drawn independently and uniformly at random:

$(Y_0,\dots ,Y_{k-1})\sim {\mathbb{𝔽}}_n^k$.

For each $i$ with $k\le i<n$, the marginal distribution of $Y_i$ is then defined as

$Y_i=Y_0+Y_1\cdot i+Y_2\cdot i^2+\dots +Y_{k-1}\cdot i^{k-1},$

where the calculation is done in ${\mathbb{𝔽}}_n$. (Joffe 1974) proves that the distribution $Y$ constructed in this way is $k$-wise independent as a distribution over ${\mathbb{𝔽}}_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 ${\mathbb{𝔽}}_n^k$ that have been extended to strings of length $n$ using the deterministic rule above.

Almost k-wise independent spaces

A random variable $Y$ over $\{0,1{\}}^n$ is a $\delta$-almost k-wise independent space if, for all index sets $I\subseteq \{1,\dots ,n\}$ of size $k$, the restricted distribution $Y{|}_I$ and the uniform distribution $U_k$ on $\{0,1{\}}^k$ are $\delta$-close in 1-norm, i.e., $\Vert Y{|}_I-U_k{\Vert }_1\le \delta$.

Constructions

(Naor Naor) give a general framework for combining small k-wise independent spaces with small $ϵ$-biased spaces to obtain $\delta$-almost k-wise independent spaces of even smaller size. In particular, let $G_1:\{0,1{\}}^h\to \{0,1{\}}^n$ be a linear mapping that generates a k-wise independent space and let $G_2:\{0,1{\}}^{\ell }\to \{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{\}}^{\ell }\to \{0,1{\}}^n$ with $G(x)=G_1(G_2(x))$ is a generator of an $\delta$-almost $k$-wise independent space, where $\delta =2^{k/2}ϵ$.

As mentioned above, (Alon Babai) construct a generator $G_1$ with $h=\frac{k}{2}\log n$, and (Naor Naor) construct a generator $G_2$ with $\ell =\log s=\log h+O(\log ({ϵ}^{-1}))$. Hence, the concatenation $G$ of $G_1$ and $G_2$ has seed length $\ell =\log k+\log \log n+O(\log ({ϵ}^{-1}))$. In order for $G$ to yield a $\delta$-almost k-wise independent space, we need to set $ϵ=\delta 2^{-k/2}$, which leads to a seed length of $\ell =\log \log n+O(k+\log ({\delta }^{-1}))$ and a sample space of total size $2^{\ell }\le \log n\cdot \text{poly}(2^k\cdot {\delta }^{-1})$.

References

• Alon, Noga; Babai, László; Itai, Alon (1986), "A fast and simple randomized parallel algorithm for the maximal independent set problem", Journal of Algorithms 7 (4): 567–583, doi:10.1016/0196-6774(86)90019-2, http://www.tau.ac.il/~nogaa/PDFS/Publications2/A%20fast%20and%20simple%20randomized%20parallel%20algorithm%20for%20the%20maximal%20independent%20set%20problem.pdf 
• Alon, Noga; Goldreich, Oded; Håstad, Johan; Peralta, René (1992), "Simple Constructions of Almost k-wise Independent Random Variables", Random Structures & Algorithms 3 (3): 289–304, doi:10.1002/rsa.3240030308, http://tau.ac.il/~nogaa/PDFS/aghp4.pdf 
• Ben-Aroya, Avraham; Ta-Shma, Amnon (2009). "Constructing Small-Bias Sets from Algebraic-Geometric Codes". 2009 50th Annual IEEE Symposium on Foundations of Computer Science. pp. 191–197. doi:10.1109/FOCS.2009.44. ISBN 978-1-4244-5116-6. http://www.wisdom.weizmann.ac.il/~benaroya/SmallBiasNew.pdf. 
• Chor, Benny; Goldreich, Oded; Håstad, Johan; Freidmann, Joel; Rudich, Steven; Smolensky, Roman (1985). "The bit extraction problem or t-resilient functions". 26th Annual Symposium on Foundations of Computer Science (SFCS 1985). pp. 396–407. doi:10.1109/SFCS.1985.55. ISBN 978-0-8186-0644-1. 
• Goldreich, Oded (2001), Lecture 7: Small bias sample spaces, http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l07.ps 
• Joffe, Anatole (1974), "On a Set of Almost Deterministic k-Independent Random Variables", Annals of Probability 2 (1): 161–162, doi:10.1214/aop/1176996762 
• Naor, Joseph; Naor, Moni (1990), "Small-bias probability spaces: Efficient constructions and applications", Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, pp. 213–223, doi:10.1145/100216.100244, ISBN 978-0897913614, http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias_abs.html 
• Ta-Shma, Amnon (2017), "Explicit, almost optimal, epsilon-balanced codes", Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 238–251, doi:10.1145/3055399.3055408, ISBN 9781450345286