Testing k-wise and almost k-wise independence

In this work, we consider the problems of testing whether adistribution over (0,1 ⁿ) is k-wise (resp. (,k)-wise) independentusing samples drawn from that distribution. For the problem of distinguishing k-wise independent distributions from those that are -far from k-wise independence in statistical distance, we upper bound the number ofrequired samples by (n ^k/ ²) and lower bound it by (n ^k-1/2/) (these bounds hold for constantk, and essentially the same bounds hold for general k). Toachieve these bounds, we use Fourier analysis to relate adistribution's distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a setof variables. The relationships we derive are tighter than previouslyknown, and may be of independent interest. To distinguish (,k)-wise independent distributions from thosethat are -far from (,k)-wise independence in statistical distance, we upper bound thenumber of required samples by O(k log n / ²²) and lower bound it by ( k log n / 2 ^k(+) log 1/2 ^k(+)). Although these bounds are anexponential improvement (in terms of n and k) over thecorresponding bounds for testing k-wise independence, we give evidence thatthe time complexity of testing (,k)-wise independence isunlikely to be poly(n,1/,1/) for k=(log n),since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs. Under the conjecture, ourresult implies that for, say, k = log n and = 1 / n ^0.99,there is a set of (,k)-wise independent distributions, and a set of distributions at distance =1/n ^0.51 from (,k)-wiseindependence, which are indistinguishable by polynomial time algorithms.