## Abstract

In this work, we consider the problems of testing whether adistribution over (0,1 ^{n}) 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}/ ^{2}) 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 / ^{22}) 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.

Original language | English (US) |
---|---|

Title of host publication | STOC'07 |

Subtitle of host publication | Proceedings of the 39th Annual ACM Symposium on Theory of Computing |

Pages | 496-505 |

Number of pages | 10 |

DOIs | |

State | Published - 2007 |

Externally published | Yes |

Event | STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | STOC'07: 39th Annual ACM Symposium on Theory of Computing |
---|---|

Country/Territory | United States |

City | San Diego, CA |

Period | 6/11/07 → 6/13/07 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Almost k-wise independence
- Fourier analysis
- Hidden clique
- K-wise independence
- Property testing