Small-bias Probability Spaces: efficient constructions
and Applications
Joseph Naor and Moni Naor
Abstract:
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:
-
Moni Naor, Constructing Ramsey graphs from small probability spaces,
Postscript
,
gzipped
Postscript
-
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
,
Postscript
,
gzipped
Postscript
Back to On-Line Publications
Back Home