TR02-048 Authors: Noga Alon, Oded Goldreich, Yishay Mansour

Publication: 5th August 2002 11:47

Downloads: 1335

Keywords:

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.