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 language | English (US) |
---|---|
Pages (from-to) | 107-110 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 88 |
Issue number | 3 |
DOIs | |
State | Published - Nov 15 2003 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications