On using deterministic functions to reduce randomness in probabilistic algorithms

We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n 2, and s random points, it is possible to generate deterministically from them s + k points such that the probability of not hitting the unknown set is exponentially smaller in k than 2 −s. Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.

Authors

• Miklos Santha

Keywords

No keywords are indexed for this paper.