|Title:||A SIHPLE CONSTRUCTION OF ALMOST k-Wise INDEPENDENT RANDOM VARIABLES
|Authors:||O. Goldreich and J. Hastad
|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.|
|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/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