Small-bias Probability Spaces: efficient constructions and Applications

Joseph Naor and  Moni Naor


This paper introduces and constructs small-bias probabiltiy spaces, i.e. 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. In general they are a ``cheap"  approximation to random variables that are completely independent. To sample from a k-wise e-biased collection of n  random variables the number of bits needed is O(log k +loglog n +log (1/e).

Applications of e-biased random variables include: derandomization of algorithms, communication complexity, construction of hash functions to distinguish sets and checking the combinatorial circuits.

Postscript, gzipped Postscript.

Related On-Line Papers:

Back to On-Line Publications

Back Home