Testing k-wise and almost k-wise independence

ABSTRACT

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.

References

1. N. Alon. Problems and results in extremal combinatorics (Part I). Discrete Math., 273:31--53, 2003.
2. N. Alon, L. Babai, and A. Itai. A fast and simple randomized algorithm for the maximal independent set problem. J. of Algorithms, 7:567--583, 1986.
3. N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289--304, 1992. Earlier version in FOCS'90.
4. N. Alon, O. Goldreich, and Y. Mansour. Almost k-wise independence versus k-wise independence. Inform. Process. Lett., 88:107--110, 2003.
5. N. Alon, M. Krivelevich, and B. Sudakov. Finding a large hidden clique in a random graph. Random Structures and Algorithms, 13:457--466, 1998.
6. N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, second edition, 2000.
7. T. Batu, E. Fisher, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 442--451, 2001.
8. T. Batu, L. Fortnow, R. Rubinfeld, W.D. Smith, and P. White. Testing that distributions are close. In Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, pages 189--197, 2000.
9. T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proc. 36th Annual ACM Symposium on the Theory of Computing, pages 381--390, New York, NY, USA, 2004. ACM Press.
10. W. Beckner. Inequalities in fourier analysis. Annals of Mathematics, 102:159--182, 1975.
11. S. Bernstein. The Theory of Probabilities. Gostehizdat Publishing House, Moscow, 1946.
12. A. Bonami. Etude des coefficients fourier des fonctiones de l^p(g). Ann. Inst. Fourier (Grenoble), 20(2):335--402, 1970.
13. B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky. The bit extraction problem and t-resilient functions. In Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, pages 396--407, 1985.
14. I. Dinur, E. Friedgut, G. Kindler, and R. O'Donnell. On the Fourier tails of bounded functions over the discrete cube. In Proc. 38th Annual ACM Symposium on the Theory of Computing, pages 437--446, New York, NY, USA, 2006. ACM Press.
15. U. Feige and R. Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random Structures and Algorithms, 16:195--208, 2000.
16. A. Frieze and C. McDiarmid. Algorithmic theory of random graphs. Random Structures and Algorithms, 10(1-2):5--42, 1997.
17. O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Technical Report TR00-020, Electronic Colloquium on Computational Complexity, 2000.
18. M. Jerrum. Large cliques elude the metropolis process. Random Structures and Algorithms, 3(4):347--359, 1992.
19. A. Joffe. On a set of almost deterministic k-independent random variables. Annals of Probability, 2:161--162, 1974.
20. A. Juels and M. Peinado. Hiding cliques for cryptographic security. Des. Codes Cryptography, 20(3):269--280, 2000.
21. R. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4):762--773, 1985.
22. R.M. Karp. The probabilistic analysis of some combinatorial search algorithms. In JF. Traub, editor, Algorithms and Complexity: New directions and Recent Results, pages 1--19, New York, 1976. Academic Press.
23. L. Kucera. Expected complexity of graph partitioning problems. Disc. Applied Math., 57(2-3):193--212, 1995.
24. M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Comput., 15(4):1036--1053, 1986. Earlier version in STOC'85.
25. J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Comput., 22(4):838--856, 1993. Earlier version in STOC'90.
26. R. Rubinfeld and R.A. Servedio. Testing monotone high-dimensional distributions. In Proc. 37th Annual ACM Symposium on the Theory of Computing, pages 147--156, New York, NY, USA, 2005. ACM Press.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Distribution functions