Simple Constructions of Almost k‐wise Independent Random Variables

Noga Alon, Oded Goldreich, Johan Håstad, René Peralta

Research output: Contribution to journalArticlepeer-review

365 Scopus citations

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 + o(1)) (log log n + k/2 + log 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 Naor and Naor (our size bound is better as long as ϵ < 1/(k log n)). An additional advantage of our constructions is their simplicity.

Original languageEnglish (US)
Pages (from-to)289-304
Number of pages16
JournalRandom Structures & Algorithms
Volume3
Issue number3
DOIs
StatePublished - 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Probabilistic computation
  • removing randomness
  • shiftregister sequences
  • small probability spaces

Fingerprint

Dive into the research topics of 'Simple Constructions of Almost k‐wise Independent Random Variables'. Together they form a unique fingerprint.

Cite this