ECCC-Report TR02-048https://eccc.weizmann.ac.il/report/2002/048Comments and Revisions published for TR02-048en-usMon, 05 Aug 2002 11:47:35 +0300
Paper TR02-048
| Almost $k$-wise independence versus $k$-wise independence |
Noga Alon,
Oded Goldreich,
Yishay Mansour
https://eccc.weizmann.ac.il/report/2002/048
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.
Mon, 05 Aug 2002 11:47:35 +0300https://eccc.weizmann.ac.il/report/2002/048