On using deterministic functions to reduce randomness in probabilistic algorithms (Q1094137)

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.