Almost k-wise independence versus k-wise independence

摘要

We say that a distribution over {0, 1}~n is (ε, 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 (ε, k)-wise independent distributions is how close they are to some k-wise independent distribution. We show that there exist (ε, k)-wise independent distributions whose statistical distance is at least n~(O(k)) ·ε from any i-wise independent distribution. In addition, we show that for any (ε, k)-wise independent distribution there exists some k-wise independent distribution, whose statistical distance is n~(O(k)) ·ε.