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.