Smallbias Probability Spaces: efficient constructions
and Applications
Joseph Naor and Moni Naor
Abstract:
This paper introduces and constructs smallbias 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 ebiased
random variables. In general they are a ``cheap" approximation to
random variables that are completely independent. To sample from a kwise
ebiased collection
of n random variables the number of bits needed
is O(log k +loglog n +log (1/e).
Applications of ebiased
random variables include: derandomization of algorithms, communication
complexity, construction of hash functions to distinguish sets and checking
the combinatorial circuits.
Postscript, gzipped Postscript.
Related OnLine 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. 434449. Abstract
,
Postscript
,
gzipped
Postscript
Back to OnLine Publications
Back Home