en>Aleph0: A missing alpha in the definition of reduction procedure

2014-10-31T07:43:15Z

A missing alpha in the definition of reduction procedure

en>VladimirReshetnikov at 22:27, 9 February 2012

2012-02-09T22:27:16Z

New page

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.
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]]

Alpha recursion theory - Revision history

en>Aleph0: A missing alpha in the definition of reduction procedure

en>VladimirReshetnikov at 22:27, 9 February 2012