Small-bias probability spaces: efficient constructions and applications

Joseph Naor, Moni Naor

1990 · 198 citations · 31 references

DOIFull text

Open access

Concepts

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.

References

31