Small-Bias Probability Spaces: Efficient Constructions and Applications

It is shown how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with “almost” equal probability. They are called $\epsilon $-biased random variables. The number of random bits needed to generate the random variables is $O(\log n + \log \frac{1}{\epsilon })$. Thus, if $\epsilon $ is polynomially small, then the size of the sample space is also polynomial. Random variables that are $\epsilon $-biased can be used to construct “almost” k-wise independent random variables where $\epsilon $ is a function of k. These probability spaces have various applications: l. Derandomization of algorithms: Many randomized algorithms that require only k-wise independence of their random bits (where k is bounded by $O(\log n)$), can be derandomized by using $\epsilon $-biased random variables. 2. Reducing the number of random bits required by certain randomized algorithms, e.g., verification of matrix multiplication. 3. Exhaustive testing of combinatorial circuits. The smallest known family for such testing is provided. 4. Communication complexity: Two parties can verify equality of strings with high probability exchanging only a logarithmic number of bits. 5. Hash functions: A polynomial sized family of hash functions such that with high probability the sum of a random function over two different sets is not equal can be constructed.