# Technical Report CS0775

 TR#: CS0775 Class: CS Title: TINY FAMILIES OF MIXING FUNCTIONS. Authors: O. Goldreich and A. Wigderson PDF CS0775.pdf Abstract: We present tiny families of efficiently constructible functions which possess a mixing property. Namely, for every desired error parameter \epsilon, we present a family of poly(1/\epsilon) functions, each mapping n-bit strings to n-bit strings that such that for every two sets A, B \Subset \{0,1\}^N, all but an \epsilon fraction of the functions f satisfy \Left | {\Rm Prob}(X_N \In A \Wedge F(X_N) \In B - \Frac{|A|}{2^N} \Cdot \Frac{|B|}{2^N} \Right | < \Epsilon where X_n is a random variable uniformly distributed in \{0,1\}^n. Applications to reducing the randomness complexity in sampling and in Nisan's generalization of randomized logspace computation are presented. Specifically, we save a factor of 2 in sampling and a logarithmic factor in the context of running simultaneously several randomized algorithms so that their outputs are further processed by a single logspace machine. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0775), rather than to the URL of the PDF files directly. The latter URLs may change without notice.