TY - JOUR

T1 - Almost k-wise independence versus k-wise independence

AU - Alon, Noga

AU - Goldreich, Oded

AU - Mansour, Yishay

N1 - Funding Information:
* Corresponding author. E-mail address: oded@wisdom.weizmann.ac.il (O. Goldreich). 1 Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. 2 Supported by the MINERVA Foundation, Germany. 3 Research supported in part by a grant from the Israel Science Foundation.

PY - 2003/11/15

Y1 - 2003/11/15

N2 - 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 nO(k)· from any k-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 nO(k)·.

AB - 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 nO(k)· from any k-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 nO(k)·.

KW - Almost k-wise independent distributions

KW - Combinatorial problems

KW - Small probability spaces

KW - Small-bias probability spaces

KW - Theory of computation

KW - k-wise independent distributions

UR - http://www.scopus.com/inward/record.url?scp=0141595861&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0141595861&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(03)00359-4

DO - 10.1016/S0020-0190(03)00359-4

M3 - Article

AN - SCOPUS:0141595861

VL - 88

SP - 107

EP - 110

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -