首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号