Technical Report CS0775

TR#:CS0775
Class:CS
Title: TINY FAMILIES OF MIXING FUNCTIONS.
Authors: O. Goldreich and A. Wigderson
PDFCS0775.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.

CopyrightThe 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.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin