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: [email protected] (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
SN - 0020-0190
VL - 88
SP - 107
EP - 110
JO - Information Processing Letters
JF - Information Processing Letters
IS - 3
ER -