Testing k-wise and almost k-wise independence

Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

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 languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages496-505
Number of pages10
DOIs
StatePublished - Oct 30 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/11/076/13/07

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint Dive into the research topics of 'Testing k-wise and almost k-wise independence'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., & Xie, N. (2007). Testing k-wise and almost k-wise independence. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 496-505). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250863