small-bias sample space

Let $X$ be a probability distribution over $\backslash \{0,1\backslash \}^n$.

The bias of $X$ with respect to a set of indices $I\; \backslash subseteq\; \backslash \{1,\backslash dots,n\backslash \}$ is defined ascf., e.g., {{harvtxt|Goldreich|2001}}

:$$

\text{bias}_I(X)

=

\left|

\Pr_{x\sim X} \left(\sum_{i\in I} x_i = 0\right)

-

\Pr_{x\sim X} \left(\sum_{i\in I} x_i = 1\right)

\right|

=

\left|

2 \cdot \Pr_{x\sim X} \left(\sum_{i\in I} x_i = 0\right)

-1

\right|

\,,

where the sum is taken over $\backslash mathbb\; F\_2$, the finite field with two elements. In other words, the sum $\backslash sum\_\{i\backslash in\; I\}\; x\_i$ equals $0$ if the number of ones in the sample $x\backslash in\backslash \{0,1\backslash \}^n$ at the positions defined by $I$ is even, and otherwise, the sum equals $1$.

For $I=\backslash emptyset$, the empty sum is defined to be zero, and hence $\backslash text\{bias\}\_\{\backslash emptyset\}\; (X)\; =\; 1$.

A probability distribution $X$ over $\backslash \{0,1\backslash \}^n$ is called an $\backslash epsilon$-biased sample space if

\text{bias}_I(X) \leq \epsilon

holds for all non-empty subsets $I\; \backslash subseteq\; \backslash \{1,2,\backslash ldots,n\backslash \}$.

An $\backslash epsilon$-biased sample space $X$ that is generated by picking a uniform element from a multiset $X\backslash subseteq\; \backslash \{0,1\backslash \}^n$ is called $\backslash epsilon$-biased set.

The size $s$ of an $\backslash epsilon$-biased set $X$ is the size of the multiset that generates the sample space.

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

There is a close connection between $\backslash epsilon$-biased sets and $\backslash epsilon$-balanced linear error-correcting codes.

A linear code $C:\backslash \{0,1\backslash \}^n\backslash to\backslash \{0,1\backslash \}^s$ of message length $n$ and block length $s$ is

$\backslash epsilon$-balanced if the Hamming weight of every nonzero codeword $C(x)$ is between $(\backslash frac\{1\}\{2\}-\backslash epsilon)s$ and $(\backslash frac\{1\}\{2\}+\backslash epsilon)s$.

Since $C$ is a linear code, its generator matrix is an $(n\backslash times\; s)$-matrix $A$ over $\backslash mathbb\; F\_2$ with $C(x)=x\; \backslash cdot\; A$.

Then it holds that a multiset $X\backslash subset\backslash \{0,1\backslash \}^\{n\}$ is $\backslash epsilon$-biased if and only if the linear code $C\_X$, whose columns are exactly elements of $X$, is $\backslash epsilon$-balanced.cf., e.g., p. 2 of {{harvtxt|Ben-Aroya|Ta-Shma|2009}}

Usually the goal is to find $\backslash epsilon$-biased sets that have a small size $s$ relative to the parameters $n$ and $\backslash epsilon$.

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/\backslash epsilon^2)$.

The construction is non-explicit in the sense that finding the $\backslash epsilon$-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 $\backslash epsilon$-biased sets is $s=\backslash Omega(n/\; (\backslash epsilon^2\; \backslash log\; (1/\backslash epsilon))$, that is, in order for a set to be $\backslash epsilon$-biased, it must be at least that big.

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

• {{harvtxt|Naor|Naor|1990}} achieve $\backslash displaystyle\; s=\; \backslash frac\{n\}\{\backslash text\{poly\}(\backslash epsilon)\}$. 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.
• {{harvtxt|Alon|Goldreich|Håstad|Peralta|1992}} achieve $\backslash displaystyle\; s=\; O\backslash left(\backslash frac\{n\}\{\backslash epsilon\; \backslash log\; (n/\backslash epsilon)\}\backslash right)^2$. One of their constructions is the concatenation of Reed–Solomon codes with the Hadamard code; this concatenation turns out to be an $\backslash epsilon$-balanced code, which gives rise to an $\backslash epsilon$-biased sample space via the connection mentioned above.
• Concatenating Algebraic geometric codes with the Hadamard code gives an $\backslash epsilon$-balanced code with $\backslash displaystyle\; s=\; O\backslash left(\backslash frac\{n\}\{\backslash epsilon^3\; \backslash log\; (1/\backslash epsilon)\}\backslash right)$.
• {{harvtxt|Ben-Aroya|Ta-Shma|2009}} achieves $\backslash displaystyle\; s=\; O\backslash left(\backslash frac\{n\}\{\backslash epsilon^2\; \backslash log\; (1/\backslash epsilon)\}\backslash right)^\{5/4\}$.
• {{harvtxt|Ta-Shma|2017}} achieves $\backslash displaystyle\; s=\; O\backslash left(\backslash frac\{n\}\{\backslash epsilon^\{2+o(1)\}\}\backslash right)$ which is almost optimal because of the lower bound.

These bounds are mutually incomparable. In particular, none of these constructions yields the smallest $\backslash epsilon$-biased sets for all settings of $\backslash epsilon$ 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 $\backslash \{0,1\backslash \}^n$ is a k-wise independent space if, for all index sets $I\backslash subseteq\backslash \{1,\backslash dots,n\backslash \}$ of size $k$, the marginal distribution $Y|\_I$ is exactly equal to the uniform distribution over $\backslash \{0,1\backslash \}^k$.

That is, for all such $I$ and all strings $z\backslash in\backslash \{0,1\backslash \}^k$, the distribution $Y$ satisfies $\backslash Pr\_Y\; (Y|\_I\; =\; z)\; =\; 2^\{-k\}$.

k-wise independent spaces are fairly well understood.

• A simple construction by {{harvtxt|Joffe|1974}} achieves size $n^k$.
• {{harvtxt|Alon|Babai|Itai|1986}} construct a k-wise independent space whose size is $n^\{k/2\}$.
• {{harvtxt|Chor|Goldreich|Håstad|Freidmann|1985}} prove that no k-wise independent space can be significantly smaller than $n^\{k/2\}$.

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

:$(Y\_0,\backslash dots,Y\_\{k-1\})\; \backslash sim\backslash mathbb\; F\_n^k$.

For each $i$ with , the marginal distribution of $Y\_i$ is then defined as

:$Y\_i=Y\_0\; +\; Y\_1\; \backslash cdot\; i\; +\; Y\_2\; \backslash cdot\; i^2\; +\; \backslash dots\; +\; Y\_\{k-1\}\; \backslash cdot\; i^\{k-1\}\backslash ,,$

where the calculation is done in $\backslash mathbb\; F\_n$.

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

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

{{harvtxt|Naor|Naor|1990}} give a general framework for combining small k-wise independent spaces with small $\backslash epsilon$-biased spaces to obtain $\backslash delta$-almost k-wise independent spaces of even smaller size.

In particular, let $G\_1:\backslash \{0,1\backslash \}^h\backslash to\backslash \{0,1\backslash \}^n$ be a linear mapping that generates a k-wise independent space and let $G\_2:\backslash \{0,1\backslash \}^\backslash ell\; \backslash to\; \backslash \{0,1\backslash \}^h$ be a generator of an $\backslash epsilon$-biased set over $\backslash \{0,1\backslash \}^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 $\backslash epsilon$-biased.

Then $G\; :\; \backslash \{0,1\backslash \}^\backslash ell\; \backslash to\; \backslash \{0,1\backslash \}^n$ with $G(x)\; =\; G\_1(G\_2(x))$ is a generator of an $\backslash delta$-almost $k$-wise independent space, where $\backslash delta=2^\{k/2\}\; \backslash epsilon$.Section 4 in {{harvtxt|Naor|Naor|1990}}

As mentioned above, {{harvtxt|Alon|Babai|Itai|1986}} construct a generator $G\_1$ with $h=\backslash tfrac\{k\}\{2\}\; \backslash log\; n$, and {{harvtxt|Naor|Naor|1990}} construct a generator $G\_2$ with $\backslash ell=\backslash log\; s=\backslash log\; h\; +\; O(\backslash log(\backslash epsilon^\{-1\}))$.

Hence, the concatenation $G$ of $G\_1$ and $G\_2$ has seed length $\backslash ell\; =\; \backslash log\; k\; +\; \backslash log\; \backslash log\; n\; +\; O(\backslash log(\backslash epsilon^\{-1\}))$.

In order for $G$ to yield a $\backslash delta$-almost k-wise independent space, we need to set $\backslash epsilon\; =\; \backslash delta\; 2^\{-k/2\}$, which leads to a seed length of $\backslash ell\; =\; \backslash log\; \backslash log\; n\; +\; O(k+\backslash log(\backslash delta^\{-1\}))$ and a sample space of total size $2^\backslash ell\; \backslash leq\; \backslash log\; n\; \backslash cdot\; \backslash text\{poly\}(2^k\; \backslash cdot\backslash delta^\{-1\})$.

{{Reflist}}

• {{Citation

| last1 = Alon

| first1 = Noga

| last2 = Babai

| first2 = László

| last3 = Itai

| first3 = Alon

| title = A fast and simple randomized parallel algorithm for the maximal independent set problem

| year = 1986

| volume = 7

| issue = 4

| pages = 567–583

| journal = Journal of Algorithms

| doi=10.1016/0196-6774(86)90019-2

| url=http://www.tau.ac.il/~nogaa/PDFS/Publications2/A%20fast%20and%20simple%20randomized%20parallel%20algorithm%20for%20the%20maximal%20independent%20set%20problem.pdf

}}

• {{Citation

| last1 = Alon

| first1 = Noga

| last2 = Goldreich

| first2 = Oded

| last3 = Håstad

| first3 = Johan

| last4 = Peralta

| first4 = René

| title = Simple Constructions of Almost k-wise Independent Random Variables

| year = 1992

| volume = 3

| issue = 3

| pages = 289–304

| journal = Random Structures & Algorithms

| doi=10.1002/rsa.3240030308

| url=http://tau.ac.il/~nogaa/PDFS/aghp4.pdf

| citeseerx = 10.1.1.106.6442

}}

• {{Cite book|first1 = Avraham | last1= Ben-Aroya

|first2 = Amnon | last2= Ta-Shma

| title= 2009 50th Annual IEEE Symposium on Foundations of Computer Science

| chapter= Constructing Small-Bias Sets from Algebraic-Geometric Codes

|year=2009

|pages=191–197

|doi=10.1109/FOCS.2009.44

|url=http://www.wisdom.weizmann.ac.il/~benaroya/SmallBiasNew.pdf

|isbn = 978-1-4244-5116-6

| citeseerx= 10.1.1.149.9273

}}

• {{Cite book|first1 = Benny | last1=Chor | author1-link = Benny Chor

|first2 =Oded | last2=Goldreich

|first3 =Johan | last3=Håstad

|first4 =Joel | last4=Freidmann

|first5 =Steven | last5=Rudich

|first6 =Roman | last6=Smolensky

| title=26th Annual Symposium on Foundations of Computer Science (SFCS 1985) | chapter=The bit extraction problem or t-resilient functions |year=1985

|pages=396–407

|doi=10.1109/SFCS.1985.55

|url=

|isbn = 978-0-8186-0644-1

| citeseerx=10.1.1.39.6768

| s2cid=6968065

}}

• {{Citation

| last = Goldreich

| first = Oded

| author-link =

| title = Lecture 7: Small bias sample spaces

| year = 2001

| url = http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l07.ps

}}

• {{Citation

| last=Joffe | first=Anatole

| title=On a Set of Almost Deterministic k-Independent Random Variables

| year=1974

| journal=Annals of Probability

| pages=161–162

| volume=2

| issue=1

| doi=10.1214/aop/1176996762

| doi-access=free

}}

• {{Citation

| last1 = Naor

| first1 = Joseph

| last2 = Naor

| first2 = Moni

| title = Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90

| chapter = Small-bias probability spaces: Efficient constructions and applications

| year = 1990

| url = http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias_abs.html

| pages=213–223

| doi=10.1145/100216.100244

| isbn = 978-0897913614| citeseerx = 10.1.1.421.2784

| s2cid = 14031194

}}

• {{Citation

| last1 = Ta-Shma

| first1 = Amnon

| title = Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

| chapter = Explicit, almost optimal, epsilon-balanced codes

| year = 2017

| pages=238–251

| doi=10.1145/3055399.3055408

| isbn = 9781450345286| s2cid = 5648543

}}

Category:Pseudorandomness

Category:Theoretical computer science