Almost k-wise independence versus k-wise independence |
| |
Authors: | Noga Alon Oded Goldreich Yishay Mansour |
| |
Affiliation: | a Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat-Aviv, Israel b Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel c School of Computer Science, Tel Aviv University, Ramat-Aviv, Israel |
| |
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: | Combinatorial problems Theory of computation Small probability spaces k-wise independent distributions Almost k-wise independent distributions Small-bias probability spaces |
本文献已被 ScienceDirect 等数据库收录! |
|