## Almost $k$-wise independence versus $k$-wise independence

#### Webpage for a paper by Noga Alon, Oded Goldreich, and Yishay Mansour

#### Abstract

We say that a distribution over $\{0,1\}^n$
is almost $k$-wise independent
if its restriction to every $k$ coordinates results in a
distribution that is close to the uniform distribution.
A natural question regarding almost $k$-wise independent
distributions is how close they are to some $k$-wise
independent distribution. We show that the latter distance is
essentially $n^{\Theta(k)}$ times the former distance.

#### Material available on-line

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