Almost k-wise independence versus k-wise independence

Noga Alon; Oded Goldreich; Yishay Mansour

doi:10.1016/S0020-0190(03)00359-4

Almost k-wise independence versus k-wise independence

Noga Alon
, Oded Goldreich
, Yishay Mansour

Research output: Contribution to journal › Article › peer-review

41 Scopus citations

Abstract

We say that a distribution over {0,1}ⁿ 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 n^O(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 n^O(k)·.

Original language	English (US)
Pages (from-to)	107-110
Number of pages	4
Journal	Information Processing Letters
Volume	88
Issue number	3
DOIs	https://doi.org/10.1016/S0020-0190(03)00359-4
State	Published - Nov 15 2003
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Almost k-wise independent distributions
Combinatorial problems
Small probability spaces
Small-bias probability spaces
Theory of computation
k-wise independent distributions

Access to Document

10.1016/S0020-0190(03)00359-4

Cite this

@article{6005e9de69aa4522ac4da78176788aea,

title = "Almost k-wise independence versus k-wise independence",

abstract = "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)·.",

keywords = "Almost k-wise independent distributions, Combinatorial problems, Small probability spaces, Small-bias probability spaces, Theory of computation, k-wise independent distributions",

author = "Noga Alon and Oded Goldreich and Yishay Mansour",

note = "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.",

year = "2003",

month = nov,

day = "15",

doi = "10.1016/S0020-0190(03)00359-4",

language = "English (US)",

volume = "88",

pages = "107--110",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "3",

}

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 - https://www.scopus.com/pages/publications/0141595861

UR - https://www.scopus.com/pages/publications/0141595861#tab=citedBy

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 -

Almost k-wise independence versus k-wise independence

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this