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: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 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: Noga Alon , Oded Goldreich , Yishay Mansour, Almost k-wise independence versus k-wise independence, Information Processing Letters, v.88 n.3, p.107-110, 15 November 2003 [doi>10.1016/S0020-0190(03)00359-4]
• 5: Noga Alon , Michael Krivelevich , Benny Sudakov, Finding a large hidden clique in a random graph, Random Structures & Algorithms, v.13 n.3-4, p.457-466, Oct., 1998
• 6: N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, second edition, 2000.
• 7: T. Batu , L. Fortnow , E. Fischer , R. Kumar , R. Rubinfeld , P. White, Testing Random Variables for Independence and Identity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.442, October 14-17, 2001
• 8: T. Batu , L. Fortnow , R. Rubinfeld , W. D. Smith , P. White, Testing that distributions are close, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.259, November 12-14, 2000
• 9: Tugkan Batu , Ravi Kumar , Ronitt Rubinfeld, Sublinear algorithms for testing monotone and unimodal distributions, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007414]
• 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: Irit Dinur , Ehud Friedgut , Guy Kindler , Ryan O'Donnell, On the fourier tails of bounded functions over the discrete cube, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132580]
• 15: Uriel Feige , Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures & Algorithms, v.16 n.2, p.195-208, March 2000 [doi>10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A]
• 16: Alan Frieze , Colin McDiarmid, Algorithmic theory of random graphs, Random Structures & Algorithms, v.10 n.1-2, p.5-42, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.0.CO;2-Z]
• 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: Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000 [doi>10.1023/A:1008374125234]
• 21: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
• 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: Luděk Kučera, Expected complexity of graph partitioning problems, Discrete Applied Mathematics, v.57 n.2-3, p.193-212, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00103-K]
• 24: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 25: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 26: Ronitt Rubinfeld , Rocco A. Servedio, Testing monotone high-dimensional distributions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060613]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Theory

Keywords:
Fourier analysis, almost k-wise independence, hidden clique, k-wise independence, property testing