Almost k-wise independence versus k-wise independence

Noga Alon, Oded Goldreich, Yishay Mansour

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

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)·.

Original languageEnglish (US)
Pages (from-to)107-110
Number of pages4
JournalInformation Processing Letters
Volume88
Issue number3
DOIs
StatePublished - Nov 15 2003
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Almost k-wise independence versus k-wise independence'. Together they form a unique fingerprint.

Cite this