Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with $k$-wise independence:
TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

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

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 ... more >>>

ISSN 1433-8092 | Imprint