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

Noga Alon; Oded Goldreich; Yishay Mansour

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR02-048 | 31st July 2002 00:00

Almost k-wise independence versus k-wise independence

TR02-048 Authors: Noga Alon, Oded Goldreich, Yishay Mansour
Publication: 5th August 2002 11:47
Downloads: 2448

Keywords:

k-wise independence, derandomization, small bias probability spaces, Small sample spaces

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.

ISSN 1433-8092 | Imprint