Technical Report CS0673

 TR#: CS0673 Class: CS Title: SIMPLE CONSTRUCTIONS OF ALMOST {\em k}-wise INDEPENDENT RANDOM VARIABLES Authors: N. Alon, O. Goldreich, J. Hastad, R. Peralta PDF - Revised CS0673.revised.pdf Abstract: We present three alternative simple constructions of small probability spaces on $n$ bits for which any $k$ bits are almost independent. The number of bits used to specify a point in the sample space is $(2 + 0(1))($ log log $n +$ log $k +$log $\frac{1}{\varepsilon}$), where $\varepsilon$ is the statistical difference between the distribution induced on any $k$ bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as $\varepsilon < 1/(k\ \mbox{log}\ n)$). An additional advantage of our constructions is their simplicity. 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/1991/CS/CS0673), rather than to the URL of the PDF files directly. The latter URLs may change without notice.