{{More footnotes needed|date=June 2020}} In theoretical computer science, a '''small-bias sample space''' (also known as '''<math>\epsilon</math>-biased sample space''', '''<math>\epsilon</math>-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 <math>\epsilon</math>-biased sample spaces are ''equivalent'' to '''<math>\epsilon</math>-balanced error-correcting codes'''.
==Definition==
===Bias=== Let <math>X</math> be a probability distribution over <math>\{0,1\}^n</math>. The ''bias'' of <math>X</math> with respect to a set of indices <math>I \subseteq \{1,\dots,n\}</math> is defined as<ref>cf., e.g., {{harvtxt|Goldreich|2001}}</ref> :<math> \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| \,,</math> where the sum is taken over <math>\mathbb F_2</math>, the finite field with two elements. In other words, the sum <math>\sum_{i\in I} x_i</math> equals <math>0</math> if the number of ones in the sample <math>x\in\{0,1\}^n</math> at the positions defined by <math>I</math> is even, and otherwise, the sum equals <math>1</math>. For <math>I=\emptyset</math>, the empty sum is defined to be zero, and hence <math>\text{bias}_{\emptyset} (X) = 1</math>.
=== ϵ-biased sample space === A probability distribution <math>X</math> over <math>\{0,1\}^n</math> is called an ''<math>\epsilon</math>-biased sample space'' if <math> \text{bias}_I(X) \leq \epsilon </math> holds for all non-empty subsets <math>I \subseteq \{1,2,\ldots,n\}</math>.
=== ϵ-biased set === An <math>\epsilon</math>-biased sample space <math>X</math> that is generated by picking a uniform element from a multiset <math>X\subseteq \{0,1\}^n</math> is called ''<math>\epsilon</math>-biased set''. The ''size'' <math>s</math> of an <math>\epsilon</math>-biased set <math>X</math> is the size of the multiset that generates the sample space.
=== ϵ-biased generator === An <math>\epsilon</math>-biased generator <math>G:\{0,1\}^\ell \to \{0,1\}^n</math> is a function that maps strings of length <math>\ell</math> to strings of length <math>n</math> such that the multiset <math>X_G=\{G(y) \;\vert\; y\in\{0,1\}^\ell \}</math> is an <math>\epsilon</math>-biased set. The ''seed length'' of the generator is the number <math>\ell</math> and is related to the size of the <math>\epsilon</math>-biased set <math>X_G</math> via the equation <math>s=2^\ell</math>.
== Connection with epsilon-balanced error-correcting codes == There is a close connection between <math>\epsilon</math>-biased sets and ''<math>\epsilon</math>-balanced'' linear error-correcting codes. A linear code <math>C:\{0,1\}^n\to\{0,1\}^s</math> of message length <math>n</math> and block length <math>s</math> is ''<math>\epsilon</math>-balanced'' if the Hamming weight of every nonzero codeword <math>C(x)</math> is between <math>(\frac{1}{2}-\epsilon)s</math> and <math>(\frac{1}{2}+\epsilon)s</math>. Since <math>C</math> is a linear code, its generator matrix is an <math>(n\times s)</math>-matrix <math>A</math> over <math>\mathbb F_2</math> with <math>C(x)=x \cdot A</math>.
Then it holds that a multiset <math>X\subset\{0,1\}^{n}</math> is <math>\epsilon</math>-biased if and only if the linear code <math>C_X</math>, whose columns are exactly elements of <math>X</math>, is <math>\epsilon</math>-balanced.<ref name="BA-TS-09">cf., e.g., p. 2 of {{harvtxt|Ben-Aroya|Ta-Shma|2009}}</ref>
== Constructions of small epsilon-biased sets == Usually the goal is to find <math>\epsilon</math>-biased sets that have a small size <math>s</math> relative to the parameters <math>n</math> and <math>\epsilon</math>. This is because a smaller size <math>s</math> 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 <math>s=O(n/\epsilon^2)</math>.<ref name="BA-TS-09" /> The construction is non-explicit in the sense that finding the <math>\epsilon</math>-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 <math>\epsilon</math>-biased sets is <math>s=\Omega(n/ (\epsilon^2 \log (1/\epsilon))</math>, that is, in order for a set to be <math>\epsilon</math>-biased, it must be at least that big.<ref name="BA-TS-09" />
=== Explicit constructions === There are many explicit, i.e., deterministic constructions of <math>\epsilon</math>-biased sets with various parameter settings: * {{harvtxt|Naor|Naor|1990}} achieve <math>\displaystyle s= \frac{n}{\text{poly}(\epsilon)}</math>. 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 <math>\displaystyle s= O\left(\frac{n}{\epsilon \log (n/\epsilon)}\right)^2</math>. One of their constructions is the concatenation of Reed–Solomon codes with the Hadamard code; this concatenation turns out to be an <math>\epsilon</math>-balanced code, which gives rise to an <math>\epsilon</math>-biased sample space via the connection mentioned above. * Concatenating Algebraic geometric codes with the Hadamard code gives an <math>\epsilon</math>-balanced code with <math>\displaystyle s= O\left(\frac{n}{\epsilon^3 \log (1/\epsilon)}\right)</math>.<ref name="BA-TS-09" /> * {{harvtxt|Ben-Aroya|Ta-Shma|2009}} achieves <math>\displaystyle s= O\left(\frac{n}{\epsilon^2 \log (1/\epsilon)}\right)^{5/4}</math>. * {{harvtxt|Ta-Shma|2017}} achieves <math>\displaystyle s= O\left(\frac{n}{\epsilon^{2+o(1)}}\right)</math> which is almost optimal because of the lower bound. These bounds are mutually incomparable. In particular, none of these constructions yields the smallest <math>\epsilon</math>-biased sets for all settings of <math>\epsilon</math> and <math>n</math>.
== 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 <math>Y</math> over <math>\{0,1\}^n</math> is a ''k-wise independent space'' if, for all index sets <math>I\subseteq\{1,\dots,n\}</math> of size <math>k</math>, the marginal distribution <math>Y|_I</math> is exactly equal to the uniform distribution over <math>\{0,1\}^k</math>. That is, for all such <math>I</math> and all strings <math>z\in\{0,1\}^k</math>, the distribution <math>Y</math> satisfies <math>\Pr_Y (Y|_I = z) = 2^{-k}</math>.
==== Constructions and bounds ==== k-wise independent spaces are fairly well understood. * A simple construction by {{harvtxt|Joffe|1974}} achieves size <math>n^k</math>. * {{harvtxt|Alon|Babai|Itai|1986}} construct a k-wise independent space whose size is <math>n^{k/2}</math>. * {{harvtxt|Chor|Goldreich|Håstad|Freidmann|1985}} prove that no k-wise independent space can be significantly smaller than <math>n^{k/2}</math>.
==== Joffe's construction ==== {{harvtxt|Joffe|1974}} constructs a <math>k</math>-wise independent space <math>Y</math> over the finite field with some prime number <math>n>k</math> of elements, i.e., <math>Y</math> is a distribution over <math>\mathbb F_n^n</math>. The initial <math>k</math> marginals of the distribution are drawn independently and uniformly at random: :<math>(Y_0,\dots,Y_{k-1}) \sim\mathbb F_n^k</math>. For each <math>i</math> with <math>k \leq i < n</math>, the marginal distribution of <math>Y_i</math> is then defined as :<math>Y_i=Y_0 + Y_1 \cdot i + Y_2 \cdot i^2 + \dots + Y_{k-1} \cdot i^{k-1}\,,</math> where the calculation is done in <math>\mathbb F_n</math>. {{harvtxt|Joffe|1974}} proves that the distribution <math>Y</math> constructed in this way is <math>k</math>-wise independent as a distribution over <math>\mathbb F_n^n</math>. The distribution <math>Y</math> is uniform on its support, and hence, the support of <math>Y</math> forms a ''<math>k</math>-wise independent set''. It contains all <math>n^k</math> strings in <math>\mathbb F_n^k</math> that have been extended to strings of length <math>n</math> using the deterministic rule above.
=== Almost k-wise independent spaces === A random variable <math>Y</math> over <math>\{0,1\}^n</math> is a ''<math>\delta</math>-almost k-wise independent space'' if, for all index sets <math>I\subseteq\{1,\dots,n\}</math> of size <math>k</math>, the restricted distribution <math>Y|_I</math> and the uniform distribution <math>U_k</math> on <math>\{0,1\}^k</math> are <math>\delta</math>-close in 1-norm, i.e., <math>\Big\|Y|_I - U_k\Big\|_1 \leq \delta</math>.
==== Constructions ==== {{harvtxt|Naor|Naor|1990}} give a general framework for combining small k-wise independent spaces with small <math>\epsilon</math>-biased spaces to obtain <math>\delta</math>-almost k-wise independent spaces of even smaller size. In particular, let <math>G_1:\{0,1\}^h\to\{0,1\}^n</math> be a linear mapping that generates a k-wise independent space and let <math>G_2:\{0,1\}^\ell \to \{0,1\}^h</math> be a generator of an <math>\epsilon</math>-biased set over <math>\{0,1\}^h</math>. That is, when given a uniformly random input, the output of <math>G_1</math> is a k-wise independent space, and the output of <math>G_2</math> is <math>\epsilon</math>-biased. Then <math>G : \{0,1\}^\ell \to \{0,1\}^n</math> with <math>G(x) = G_1(G_2(x))</math> is a generator of an <math>\delta</math>-almost <math>k</math>-wise independent space, where <math>\delta=2^{k/2} \epsilon</math>.<ref>Section 4 in {{harvtxt|Naor|Naor|1990}}</ref>
As mentioned above, {{harvtxt|Alon|Babai|Itai|1986}} construct a generator <math>G_1</math> with <math>h=\tfrac{k}{2} \log n</math>, and {{harvtxt|Naor|Naor|1990}} construct a generator <math>G_2</math> with <math>\ell=\log s=\log h + O(\log(\epsilon^{-1}))</math>. Hence, the concatenation <math>G</math> of <math>G_1</math> and <math>G_2</math> has seed length <math>\ell = \log k + \log \log n + O(\log(\epsilon^{-1}))</math>. In order for <math>G</math> to yield a <math>\delta</math>-almost k-wise independent space, we need to set <math>\epsilon = \delta 2^{-k/2}</math>, which leads to a seed length of <math>\ell = \log \log n + O(k+\log(\delta^{-1}))</math> and a sample space of total size <math>2^\ell \leq \log n \cdot \text{poly}(2^k \cdot\delta^{-1})</math>.
== Notes == {{Reflist}}
== References ==
* {{Citation | last1 = Alon | first1 = Noga |author-link=Noga Alon | 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=https://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=https://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 = https://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