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

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


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.