Technical Report CS0638

TR#:CS0638
Class:CS
Title: A SIHPLE CONSTRUCTION OF ALMOST k-Wise INDEPENDENT RANDOM VARIABLES
Authors: O. Goldreich and J. Hastad
PDFCS0638.pdf
Abstract: We present a simple construction of a small probability space 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 O(log log n + k + log ~), where e is the statistical difference between of 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. An additional advantage of our construction is its simplicity. Loosely speaking, the sample space consists of the set of sequences obtained from a linear feedback shift register on various short start and feedback sequences.
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/1990/CS/CS0638), 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 1990
To the main CS technical reports page

Computer science department, Technion
admin