Small-Bias Probability Spaces: Efficient Constructions and Applications

Publisher Website
Google Scholar
Abstract
We show 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 e-biased random variables. The number of random bits needed to generate the random variables is O(logn ÷ log ~). Thus, if e is polynomially small, then the size of the sample space is also polynomial. e-biased random variables can be used to construct "almost" k-wise independent random variables where e is a function of k. Applications are shown to derandomization of algorithms, reducing the number of random bits required by certain randomized algorithms, exhaustive testing of combinatorial circuits, communication complexity and construction of hash functions.

This publication has 21 references indexed in Scilit: