Simple constructions of almost k-wise independent random variables

Noga Alon, Oded Goldreich, Johan Hastad, Rene Peralta

Research output: Contribution to journalConference article

78 Scopus citations

Abstract

The authors 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 O(log log n + k + log 1/ε), where ε 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 J. Naor and M. Naor (1990). An advantage of the present constructions is their simplicity. Two of the constructions are based on bit sequences that are widely believed to possess randomness properties, and the results can be viewed as an explanation and establishment of these beliefs.

Original languageEnglish (US)
Pages (from-to)544-553
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2
StatePublished - Dec 1 1990
Externally publishedYes
EventProceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA
Duration: Oct 22 1990Oct 24 1990

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Simple constructions of almost k-wise independent random variables'. Together they form a unique fingerprint.

  • Cite this