Small-bias Probability Spaces: efficient constructions
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
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
Moni Naor, Constructing Ramsey graphs from small probability spaces,
Noga Alon and Moni Naor, Derandomization, witnesses for Boolean matrix
multiplication and construction of perfect hash functions, Algorithmica,
vol 16, 1996, pp. 434-449. Abstract