Approximations of general independent distributions
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, 1992•dl.acm.org
We describe efficient constructions of small probability spaces that approximate the
independent distribution for general random variables. Previous work on efficient
constructions concentrate on approximations of the independent distribution for the special
case of uniform boolean-valued random variables. Our results yield efficient constructions of
small sets with low discrepancy in high dimensional space and have applications to
derandomizing randomized algorithms.
independent distribution for general random variables. Previous work on efficient
constructions concentrate on approximations of the independent distribution for the special
case of uniform boolean-valued random variables. Our results yield efficient constructions of
small sets with low discrepancy in high dimensional space and have applications to
derandomizing randomized algorithms.
We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.
ACM Digital Library