Simple Constructions of Almost $k$-wise Independent Random Variables

Webpage for a paper by Noga Alon, Oded Goldreich, Johan Hastad, and Rene Peralta

Abstract (v.o.)

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))((k/2)+(loglog n)+(log k/\epsilon))$, where $\epsilon$ 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 $\epsilon < 1/(k\log n)$). An additional advantage of our constructions is their simplicity.

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.