### 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 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 | |

State | Published - Nov 15 2003 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

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

## Cite this

Alon, N. M., Goldreich, O., & Mansour, Y. (2003). Almost k-wise independence versus k-wise independence.

*Information Processing Letters*,*88*(3), 107-110. https://doi.org/10.1016/S0020-0190(03)00359-4