Cited By
View all- Batu TFortnow LRubinfeld RSmith WWhite P(2013)Testing Closeness of Discrete DistributionsJournal of the ACM10.1145/2432622.243262660:1(1-25)Online publication date: 1-Feb-2013
Testing non-uniform k-wise independent distributions over product spaces
Pages 565 - 581
Abstract
A distribution D over Σ1 × ... × Σn is called (non-uniform) k-wise independent if for any set of k indices {i1,..., ik} and for any z1...zk ∈ Σi1×...×Σik, PrX-D[Xi1...Xik = z1 ... zk] = PrX-D[Xi1 = z1] ... PrX-D[Xik = zk]. We study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution D from the set of k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. Such a bound was previously known only for the binary field. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust. These greatly generalize the results of Alon et al. [1] on uniform k-wise independence over the binary field to non-uniform k-wise independence over product spaces. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size when k is a constant. The main technical tools employed include discrete Fourier transforms and the theory of linear systems of congruences.
References
[1]
Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., Xie, N.: Testing k-wise and almost k-wise independence. In: Proc. 39th Annual ACM Symposium on the Theory of Computing, pp. 496-505 (2007).
[2]
Alon, N., Babai, L., Itai, A.: A fast and simple randomized algorithm for the maximal independent set problem. Journal of Algorithms 7, 567-583 (1986).
[3]
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms 3(3), 289-304 (1992); Earlier version in FOCS 1990.
[4]
Alon, N., Goldreich, O., Mansour, Y.: Almost k-wise independence versus k-wise independence. Information Processing Letters 88, 107-110 (2003).
[5]
Austrin, P.: Conditional inapproximability and limited independence. PhD thesis, KTH - Royal Institute of Technology (2008), http://www.csc.kth.se/~austrin/ papers/thesis.pdf.
[6]
Azar, Y., Naor, J., Motwani, R.: Approximating probability distributions using small sample spaces. Combinatorica 18(2), 151-171 (1998).
[7]
Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P.: Testing random variables for independence and identity. In: Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 442-451 (2001).
[8]
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that distributions are close. In: Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 189-197 (2000).
[9]
Batu, T., Kumar, R., Rubinfeld, R.: Sublinear algorithms for testing monotone and unimodal distributions. In: Proc. 36th Annual ACM Symposium on the Theory of Computing, pp. 381-390. ACM Press, New York (2004).
[10]
Bertram-Kretzberg, C., Lefmann, H.: MODp-tests, almost independence and small probability spaces. Random Structures and Algorithms 16(4), 293-313 (2000).
[11]
Blais, E.: Testing juntas nearly optimally. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 151-158 (2009).
[12]
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47, 549-595 (1993); Earlier version in STOC 1900.
[13]
Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity 5(1), 96-106 (1989).
[14]
Czumaj, A., Sohler, C.: Sublinear-time algorithms. Bulletin of the European Association for Theoretical Computer Science 89, 23-47 (2006).
[15]
Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., Wan, A.: Testing for concise representations. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 549-558 (2007).
[16]
Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 39-44 (2009).
[17]
Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Structures and Algorithms 13(1), 1-16 (1998); Earlier version in STOC 1992.
[18]
Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science 75 (2001).
[19]
Goldreich, O., Goldwaser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM 45, 653-750 (1998).
[20]
Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical Report TR00-020, Electronic Colloquium on Computational Complexity (2000).
[21]
Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica 20(1), 71-86 (2000).
[22]
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1980).
[23]
Joffe, A.: On a set of almost deterministic k-independent random variables. Annals of Probability 2, 161-162 (1974).
[24]
Karloff, H., Mansour, Y.: On construction of k-wise independent random variables. In: Proc. 26th Annual ACM Symposium on the Theory of Computing, pp. 564-573 (1994).
[25]
Karp, R., Wigderson, A.: A fast parallel algorithm for the maximal independent set problem. Journal of the ACM 32(4), 762-773 (1985).
[26]
Koller, D., Megiddo, N.: Constructing small sample spaces satisfying given constraints. In: Proc. 25th Annual ACM Symposium on the Theory of Computing, pp. 268-277 (1993).
[27]
Kumar, R., Rubinfeld, R.: Sublinear time algorithms. SIGACT News 34, 57-67 (2003).
[28]
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 15(4), 1036-1053 (1986); Earlier version in STOC 1985.
[29]
Luby, M.: Removing randomness in parallel computation without a processor penalty. In: Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 162-173 (1988).
[30]
Mossel, E.: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 156-165 (2008).
[31]
Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing 22(4), 838-856 (1993); Earlier version in STOC 1990.
[32]
Neuman, C.P., Schonbach, D.I.: Discrete (Legendre) orthogonal polynomials -Asurvey. International Journal for Numerical Methods in Engineering 8, 743-770 (1974).
[33]
Nikiforov, A.F., Suslov, S.K., Uvarov, V.B.: Classical Orthogonal Polynomials of a Discrete Variable. Springer, Heidelberg (1991).
[34]
Raskhodnikova, S., Ron, D., Shpilka, A., Smith, A.: Strong lower bounds for approximating distribution support size and the distinct elements problem. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 559-569 (2007).
[35]
Ron, D.: Property testing (a tutorial). In: Pardalos, P.M., Rajasekaran, S., Reif, J., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, pp. 597-649. Kluwer Academic Publishers, Dordrecht (2001).
[36]
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing 25, 252-271 (1996).
[37]
Silvester, J.R.: Determinants of block matrices. Maths Gazette 84, 460-467 (2000).
[38]
Smith, H.J.S.: On systems of linear indeterminate equations and congruences. Phil. Trans. Royal Soc. London A 151, 293-326 (1861).
[39]
Štefankovič, D.: Fourier transform in computer science. Master's thesis, University of Chicago (2000).
[40]
Terras, A.: Fourier Analysis on Finite Groups and Applications. Cambridge University Press, Cambridge (1999).
[41]
Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. Journal of the ACM 55(1), 1-16 (2008).
Recommendations
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingAn explicit study of min-wise independent permutation families, together with their variants --- k-restricted, approximate, etc. --- was initiated by Broder, et al[4]. In this paper, we give a lower bound for the size of k-restricted min-wise independent ...
Testing k-wise and almost k-wise independence
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingIn this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.
For the problem of distinguishing k-wise independent distributions from those that ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2010
753 pages
ISBN:3642141641
Sponsors
- GDR Informatique Mathçmatique
- Conseil Régional d'Aquitaine
- Communauté Urbaine de Bordeaux
- CEA: Commissariat à l'énergie atomique et aux énergies alternatives
- INRIA: Institut Natl de Recherche en Info et en Automatique
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 06 July 2010
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025
Other Metrics
Citations
Cited By
View all- Batu TFortnow LRubinfeld RSmith WWhite P(2013)Testing Closeness of Discrete DistributionsJournal of the ACM10.1145/2432622.243262660:1(1-25)Online publication date: 1-Feb-2013