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 - RevisedCS0673.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.
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/1991/CS/CS0673), 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 1991
To the main CS technical reports page

Computer science department, Technion
admin