×

Robust characterizations of \(k\)-wise independence over product spaces and related testing results. (English) Zbl 1281.68230

Summary: A discrete distribution \(D\) over \(\Sigma _{1} \times\dots\times \Sigma _{n}\) is called (non-uniform) \(k\)-wise independent if for any subset of \(k\) indices \(\{i_{1},\ldots ,i_{k}\}\) and for any \(z_{1}\in \Sigma_{i_{1}},\ldots z_{k}\in \Sigma_{i_{k}}\), \[ \mathrm{Pr}_{X \sim D}[X_{i_{1}} \dots X_{i_{k}} = z_{1} \dots z_{k}] = \mathrm{Pr}_{X \sim D}[X_{i_{1}} = z_{1}] \dots Pr_{X \sim D}[X_{i_{k}} = z_{k}]. \] 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 \(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 when the underlying domain is \(\{0,1\}^{n}\). 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 based on our results for the uniform case. These results greatly generalize those of N. Alon et al. [“Testing \(k\)-wise and almost \(k\)-wise independence”, in: Proceedings of the 39th annual ACM symposium on the theory of computing, STOC 2007. New York, NY: ACM Press. 496–505 (2007)] on uniform \(k\)-wise independence over the Boolean cubes 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 of the distribution when \(k\) is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences.

MSC:

68W20 Randomized algorithms
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
42A16 Fourier coefficients, Fourier series of functions with special properties, special Fourier series
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon A. Andoni T. Kaufman K. Matulef R. Rubinfeld N. Xie Testing k -wise and almost k -wise independence 2007 496 505 · Zbl 1232.68093
[2] Alon, A fast and simple randomized algorithm for the maximal independent set problem, J Alg 7 pp 567– (1986) · Zbl 0631.68063 · doi:10.1016/0196-6774(86)90019-2
[3] Alon, Simple constructions of almost k -wise independent random variables, Random Struct Algorithm 3 pp 289– (1992) · Zbl 0755.60002 · doi:10.1002/rsa.3240030308
[4] Alon, Almost k -wise independence versus k -wise independence, Inform Process Lett 88 pp 107– (2003) · Zbl 1178.68251 · doi:10.1016/S0020-0190(03)00359-4
[5] Azar, Approximating probability distributions using small sample spaces, Combinatorica 18 pp 151– (1998) · Zbl 0917.60014 · doi:10.1007/PL00009813
[6] T. Batu E. Fischer L. Fortnow R. Kumar R. Rubinfeld P. White Testing random variables for independence and identity 2001 442 451
[7] T. Batu L. Fortnow R. Rubinfeld W. D. Smith P. White Testing that distributions are close 2000 189 197
[8] Batu, In Proc. of the 36th Annual ACM Symposium on the Theory of Computing pp 381– (2004)
[9] Bertram-Kretzberg, MODp -tests, almost independence and small probability spaces, Random Struct Algorithm 16 pp 293– (2000) · Zbl 0964.60003 · doi:10.1002/1098-2418(200007)16:4<293::AID-RSA1>3.0.CO;2-F
[10] E. Blais Testing juntas nearly optimally 2009 151 158 · Zbl 1304.68059
[11] Blum, Self-testing/correcting with applications to numerical problems, J Comput Syst Sci 47 pp 549– (1993) · Zbl 0795.68131 · doi:10.1016/0022-0000(93)90044-W
[12] Chor, On the power of two-point based sampling, J Complexity 5 pp 96– (1989) · Zbl 0672.60105 · doi:10.1016/0885-064X(89)90015-0
[13] Czumaj, Sublinear-time algorithms, Bull Eur Assoc Theor Comput Sci 89 pp 23– (2006) · Zbl 1169.68442
[14] de Wolf, A brief introduction to Fourier analysis on the boolean cube, Theory Comput, Graduate Surveys, TCGS 1 pp 1– (2008) · doi:10.4086/toc.gs.2008.001
[15] I. Diakonikolas H. Lee K. Matulef K. Onak R. Rubinfeld R. Servedio A. Wan Testing for concise representations 2007 549 558
[16] K. Efremenko 3-query locally decodable codes of subexponential length 2009 39 44
[17] Even, Efficient approximation of product distributions, Random Struct Algorithm 13 pp 1– (1998) · Zbl 0959.68553 · doi:10.1002/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W
[18] Fischer, The art of uninformed decisions: A primer to property testing, Bull Eur Assoc Theor Comput Sci 75 pp 97– (2001) · Zbl 1024.68045
[19] Goldreich, Property testing and its connection to learning and approximation, J ACM 45 pp 653– (1998) · Zbl 1065.68575 · doi:10.1145/285055.285060
[20] O. Goldreich D. Ron On testing expansion in bounded-degree graphs, Technical Report TR00-020 2000
[21] Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs, Combinatorica 20 pp 71– (2000) · Zbl 0949.05083 · doi:10.1007/s004930070032
[22] Hardy, An introduction to the theory of numbers (1980)
[23] Joffe, On a set of almost deterministic k -independent random variables, Ann Probab 2 pp 161– (1974) · Zbl 0276.60005 · doi:10.1214/aop/1176996762
[24] H. Karloff Y. Mansour On construction of k -wise independent random variables 1994 564 573 · Zbl 1345.68238
[25] Karp, A fast parallel algorithm for the maximal independent set problem, J ACM 32 pp 762– (1985) · Zbl 0633.68026 · doi:10.1145/4221.4226
[26] D. Koller N. Megiddo Constructing small sample spaces satisfying given constraints 1993 268 277 · Zbl 1310.68153
[27] Kumar, Sublinear time algorithms, SIGACT News 34 pp 57– (2003) · doi:10.1145/954092.954103
[28] Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J Comput 15 pp 1036– (1986) · Zbl 0619.68058 · doi:10.1137/0215074
[29] M. Luby Removing randomness in parallel computation without a processor penalty 1988 162 173
[30] E. Mossel Gaussian bounds for noise correlation of functions and tight analysis of long codes 2008 156 165
[31] Naor, Small-bias probability spaces: Efficient constructions and applications, SIAM J Comput 22 pp 838– (1993) · Zbl 0776.60014 · doi:10.1137/0222053
[32] Neuman, Discrete (Legendre) orthogonal polynomials-A survey, Int J Numer Methods Eng 8 pp 743– (1974) · Zbl 0292.65010 · doi:10.1002/nme.1620080406
[33] Nikiforov, Classical orthogonal polynomials of a discrete variable (1991) · doi:10.1007/978-3-642-74748-9
[34] S. Raskhodnikova D. Ron A. Shpilka A. Smith Strong lower bounds for approximating distribution support size and the distinct elements problem 2007 559 569 · Zbl 1194.68124
[35] Ron, Handbook of randomized computing pp 597– (2001) · doi:10.1007/978-1-4615-0013-1_15
[36] Rubinfeld, Robust characterizations of polynomials with applications to program testing, SIAM J Comput 25 pp 252– (1996) · Zbl 0844.68062 · doi:10.1137/S0097539793255151
[37] Sahai, A complete problem for statistical zero knowledge, J ACM 50 pp 1– (2003) · Zbl 1326.68165 · doi:10.1145/636865.636868
[38] Silvester, Determinants of block matrices, Maths Gazette 84 pp 460– (2000) · Zbl 02352181 · doi:10.2307/3620776
[39] Smith, On systems of linear indeterminate equations and congruences, Philos Trans R Soc London A151 pp 293– (1861) · doi:10.1098/rstl.1861.0016
[40] D. &0160;tefankovi&010D; Fourier transform in computer science, Master’s thesis 2000
[41] Terras, Fourier analysis on finite groups and applications (1999) · doi:10.1017/CBO9780511626265
[42] Yekhanin, Towards 3 -query locally decodable codes of subexponential length, J ACM 55 pp 1– (2008) · Zbl 1311.94125 · doi:10.1145/1326554.1326555
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.