Testing k-wise and Almost k-wise Independence

In this work, we consider the problems of testing whether a distribution over {0, 1}(n) is k-wise (resp. (epsilon, k)-wise) independent using samples drawn from that distribution. For the problem of distinguishing k-wise independent distributions from those that are delta-far from k-wise independence in statistical distance, we upper bound the number of required samples by (O) over tilde (n(k)/delta(2)) and lower bound it by Omega(n(k-1/2)/delta) (n f- (these bounds hold for constant k, and essentially the same bounds hold for general k). To achieve these bounds, we use Fourier analysis to relate a distribution's distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a set of variables. The relationships we derive are tighter than previously known, and may be of independent interest. To distinguish (epsilon, k)-wise independent distributions from those that are delta-far from (epsilon, k)-wise independence in statistical distance, we upper bound the number of required samples by O (klogn/delta(2)epsilon(2)) and lower bound it by Omega(root klogn/2(k)(epsilon+delta)root log1/2(k)(epsilon+delta). Although these bounds are an exponential improvement (in terms of n and k) over the corresponding bounds for testing k-wise independence, we give evidence that the time complexity of testing (epsilon, k)-wise independence is unlikely to be poly (n, 1/epsilon, 1/delta) for k = circle minus (log n), since this would disprove a plausible conjecture concerning the hardness of finding hidden cliques in random graphs. Under the conjecture, our result implies that for, say, k = log n and epsilon = 1/n(0.99), there is a set of (epsilon, k)-wise independent distributions, and a set of distributions at distance delta = 1/n(0.51) from (epsilon, k)-wise independence, which are indistinguishable by polynomial time algorithms.