
Research
Abstracts  2007 
Testing KWise and Almost KWise IndependenceN. Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld & Ning XieResults for KWise IndependenceThis work [1] studies upper and lower bound on the distance of a distribution from the set of kwise independence distributions. The bounds obtained are a quadratic improvement over similar bounds that were previously obtained by Alon Goldreich and Mansour [2]. We also turn these bounds into an almost optimal testing algorithm that gets samples from a distribution and decides whether the given distribution is kwise independent or far from any kwise independent distribution. The complexity of the testing is measured by the number of samples taken from the input distribution. Results for Almost KWise IndependenceAnother family of distributions that we study are (e,k)wise independent distributions. In these distribution every set of k variables are not independent but rather almost (with parameter e) independent. Such distributions have significantly smaller support than kwise independent distributions, and hence, are considered useful for derandomization. This work shows also almost optimal testing results for testing if a distribution is close to an (e,k)wise independent distribution. TechniquesThe main tools used are fourier analysis , convolving distributions, and using convex combinations of distribution. A conceptual contribution of out workThe original motivation of Alon, Goldreich and Mansour [2] was to show that a kwise independent distribution has an (e,k)wise independent distribution, where 'e' is large enough and these two distributions are statistically close. Such property, if true, would imply that an algorithm that requires kwise independent distribution could use instead an (e,k)wise independent distribution and still run correctly. Since the support of (e,k)wise independent distribution is small, such property could save a lot in the randomness required by the algorithm. However, this motivation was proven wrong, and hence, such distributions can't be indistinguishable by an information theoretic arguments. Here we ask whether such distributions can be computationally indistinguishable? We take a step in this direction, showing that a slight variant of this question is true under a conjecture about the hardness of the hidden clique. References:[1] N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld and N. Xie. Testing KWise and Almost KWise Independence. In Proceedings of STOC 2007, to appear. [2] N. Alon, O. Goldreich and Y. Mansour. Almost kwise Independence versus kwise Independence. In Information Processing Letters, volume 88, pp. 107110, 2003. 

