Testing Non-uniform k-Wise Independent Distributions over Product Spaces
Testing Non-uniform k-Wise Independent Distributions over Product Spaces
复制标题
测试产品空间上的非均匀 k-Wise 独立分布
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Ning Xie
中科院分区：
文献类型：
--
作者：
R. Rubinfeld;Ning Xie
A分布D / Σ1 ×…对于任意一组k个指标{i1，…， k}对于任意z1…Zk∈Σi1×…×Σ本土知识,PrX-D(ξ1…Xik = z1…zk] = PrX-D[Xi1 = z1]…PrX-D[Xik = zk]。我们研究了在乘积空间上检验（非一致）k-wise独立分布的问题。对于均匀情况，我们用D在权重不超过k的向量上的傅里叶系数的和来表示分布D与k方向独立分布集之间距离的上界。这样的上界以前只在二元场中已知。对于非均匀情况，我们给出了分布是k-独立的一个新的表征，并进一步证明了这种表征是鲁棒的。这些极大地推广了Alon et al.[1]关于二元域上一致k-独立的结果到乘积空间上的非一致k-独立。我们的结果产生了k-wise独立性的自然测试算法，当k为常数时，时间和样本复杂性在支持大小方面呈次线性。使用的主要技术工具包括离散傅里叶变换和线性同余系统理论。
A distribution D over Σ1 × ... × Σn is called (non-uniform) k-wise independent if for any set of k indices {i1,..., ik} and for any z1...zk ∈ Σi1×...×Σik, PrX-D[Xi1...Xik = z1 ... zk] = PrX-D[Xi1 = z1] ... PrX-D[Xik = zk]. We study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution D from the set of k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. Such a bound was previously known only for the binary field. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust. These greatly generalize the results of Alon et al. [1] on uniform k-wise independence over the binary field to non-uniform k-wise independence over product spaces. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size when k is a constant. The main technical tools employed include discrete Fourier transforms and the theory of linear systems of congruences.