|
|
| Line 1: |
Line 1: |
| 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 function]]s.
| | I would like to introduce myself to you, I am Jayson Simcox but I don't like when individuals use my complete name. Office supervising is exactly where her main income arrives from. To play lacross is some thing I really enjoy doing. Mississippi is exactly where her home is but her spouse desires them to move.<br><br>Here is my webpage; [http://cspl.postech.ac.kr/zboard/Membersonly/144571 free tarot readings] |
| 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 generator]]s 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 code]]s, and [[PCP theorem|probabilistically checkable proofs]].
| |
| The connection with [[error-correcting code]]s 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 code|linear error-correcting codes]].
| |
| A linear code <math>C:\{0,1\}^n\to\{0,1\}^s</math> of [[Block code#The message length k|message length]] <math>n</math> and [[Block code#The block length n|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 code]]s (which is a concatenation of [[Reed–Solomon code]]s 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 code]]s 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 code]]s 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>.
| |
| 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 (discrete)|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 [[p-norm|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 seen above, generators <math>G_1</math> exist with <math>h=k \log n</math> and generators <math>G_2</math> exist with <math>\ell=\log s=\log h + O(\log(\epsilon^{-1}))</math>.
| |
| Hence, <math>\ell = \log \log n + \log k + O(\log(\epsilon^{-1}))</math> holds.
| |
| With these settings, the generator <math>G</math> yields a <math>\delta</math>-almost <math>k</math>-wise independent set over <math>\{0,1\}^n</math> whose size is <math>2^\ell \leq \text{poly}(2^k \delta^{-1}) \cdot \log n</math>.
| |
| | |
| == Notes ==
| |
| {{Reflist}}
| |
| | |
| == References ==
| |
| | |
| * {{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
| |
| | accessdate =
| |
| | doi=10.1016/0196-6774(86)90019-2
| |
| | pdf=http://www.tau.ac.il/~nogaa/PDFS/Publications2/A%20fast%20and%20simple%20randomized%20parallel%20algorithm%20for%20the%20maximal%20independent%20set%20problem.pdf
| |
| | ref=harv}}
| |
| * {{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
| |
| | accessdate =
| |
| | doi=10.1002/rsa.3240030308
| |
| | pdf=http://tau.ac.il/~nogaa/PDFS/aghp4.pdf
| |
| | ref=harv}}
| |
| * {{Citation
| |
| |first1 = Avraham | last1= Ben-Aroya
| |
| |first2 = Amnon | last2= Ta-Shma
| |
| |ref=harv
| |
| |title=Constructing Small-Bias Sets from Algebraic-Geometric Codes
| |
| |year=2009
| |
| |journal=Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS 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
| |
| }}
| |
| * {{Citation
| |
| |first1 = Benny | last1=Chor
| |
| |first2 =Oded | last2=Goldreich
| |
| |first3 =Johan | last3=Håstad
| |
| |first4 =Joel | last4=Freidmann
| |
| |first5 =Steven | last5=Rudich
| |
| |first6 =Roman | last6=Smolensky
| |
| |ref=harv
| |
| |title=The bit extraction problem or t-resilient functions
| |
| |year=1985
| |
| |journal=Proceedings of the 26th Annual Symposium on Foundations of Computer Science, FOCS 1985
| |
| |pages=396–407
| |
| |doi=10.1109/SFCS.1985.55
| |
| |url=
| |
| |isbn = 0-8186-0644-4
| |
| }}
| |
| * {{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
| |
| | accessdate =
| |
| | ref=harv}}
| |
| * {{Citation
| |
| | last=Joffe | first=Anatole
| |
| | title=On a Set of Almost Deterministic k-Independent Random Variables
| |
| | ref=harv
| |
| | year=1974
| |
| | journal=Annals of Probability
| |
| | pages=161–162
| |
| | volume=2
| |
| | issue=1
| |
| | doi=10.1214/aop/1176996762
| |
| }}
| |
| * {{Citation
| |
| | last1 = Naor
| |
| | first1 = Joseph
| |
| | last2 = Naor
| |
| | first2 = Moni
| |
| | title = Small-bias Probability Spaces: efficient constructions and Applications
| |
| | year = 1990
| |
| | journal = Proceedings of the 22nd annual ACM symposium on Theory of computing, STOC 1990
| |
| | url = http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias_abs.html
| |
| | accessdate =
| |
| | pages=213–223
| |
| | doi=10.1145/100216.100244
| |
| | ref=harv
| |
| | isbn = 0897913612}}
| |
| | |
| [[Category:Pseudorandomness]]
| |
| [[Category:Theoretical computer science]]
| |