{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:07Z","timestamp":1725558967663},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_48","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"565-581","source":"Crossref","is-referenced-by-count":2,"title":["Testing Non-uniform k-Wise Independent Distributions over Product Spaces"],"prefix":"10.1007","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013505 (2007)","DOI":"10.1145\/1250790.1250863"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized algorithm for the maximal independent set problem. Journal of Algorithms\u00a07, 567\u2013583 (1986)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"48_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms\u00a03(3), 289\u2013304 (1992); Earlier version in FOCS 1990","journal-title":"Random Structures and Algorithms"},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(03)00359-4","volume":"88","author":"N. Alon","year":"2003","unstructured":"Alon, N., Goldreich, O., Mansour, Y.: Almost k-wise independence versus k-wise independence. Information Processing Letters\u00a088, 107\u2013110 (2003)","journal-title":"Information Processing Letters"},{"key":"48_CR5","unstructured":"Austrin, P.: Conditional inapproximability and limited independence. PhD thesis, KTH - Royal Institute of Technology (2008), http:\/\/www.csc.kth.se\/~austrin\/papers\/thesis.pdf"},{"issue":"2","key":"48_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009813","volume":"18","author":"Y. Azar","year":"1998","unstructured":"Azar, Y., Naor, J., Motwani, R.: Approximating probability distributions using small sample spaces. Combinatorica\u00a018(2), 151\u2013171 (1998)","journal-title":"Combinatorica"},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013451 (2001)","DOI":"10.1109\/SFCS.2001.959920"},{"key":"48_CR8","unstructured":"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\u2013197 (2000)"},{"key":"48_CR9","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/1007352.1007414","volume-title":"Proc. 36th Annual ACM Symposium on the Theory of Computing","author":"T. Batu","year":"2004","unstructured":"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\u2013390. ACM Press, New York (2004)"},{"issue":"4","key":"48_CR10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/1098-2418(200007)16:4<293::AID-RSA1>3.0.CO;2-F","volume":"16","author":"C. Bertram-Kretzberg","year":"2000","unstructured":"Bertram-Kretzberg, C., Lefmann, H.: MOD p -tests, almost independence and small probability spaces. Random Structures and Algorithms\u00a016(4), 293\u2013313 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"48_CR12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences\u00a047, 549\u2013595 (1993); Earlier version in STOC 1900","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"48_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity\u00a05(1), 96\u2013106 (1989)","journal-title":"Journal of Complexity"},{"key":"48_CR14","first-page":"23","volume":"89","author":"A. Czumaj","year":"2006","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. Bulletin of the European Association for Theoretical Computer Science\u00a089, 23\u201347 (2006)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"48_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"key":"48_CR16","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 39\u201344 (2009)","DOI":"10.1145\/1536414.1536422"},{"issue":"1","key":"48_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"G. Even","year":"1998","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Structures and Algorithms\u00a013(1), 1\u201316 (1998); Earlier version in STOC 1992","journal-title":"Random Structures and Algorithms"},{"key":"48_CR18","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science\u00a075 (2001)"},{"key":"48_CR19","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwaser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045, 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"48_CR20","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical Report TR00-020, Electronic Colloquium on Computational Complexity (2000)"},{"issue":"1","key":"48_CR21","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V. Grolmusz","year":"2000","unstructured":"Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica\u00a020(1), 71\u201386 (2000)","journal-title":"Combinatorica"},{"key":"48_CR22","volume-title":"An Introduction to the Theory of Numbers","author":"G.H. Hardy","year":"1980","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1980)","edition":"5"},{"key":"48_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"A. Joffe","year":"1974","unstructured":"Joffe, A.: On a set of almost deterministic k-independent random variables. Annals of Probability\u00a02, 161\u2013162 (1974)","journal-title":"Annals of Probability"},{"key":"48_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013573 (1994)","DOI":"10.1145\/195058.195409"},{"issue":"4","key":"48_CR25","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"Karp, R., Wigderson, A.: A fast parallel algorithm for the maximal independent set problem. Journal of the ACM\u00a032(4), 762\u2013773 (1985)","journal-title":"Journal of the ACM"},{"key":"48_CR26","doi-asserted-by":"crossref","unstructured":"Koller, D., Megiddo, N.: Constructing small sample spaces satisfying given constraints. In: Proc. 25th Annual ACM Symposium on the Theory of Computing, pp. 268\u2013277 (1993)","DOI":"10.1145\/167088.167168"},{"key":"48_CR27","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/954092.954103","volume":"34","author":"R. Kumar","year":"2003","unstructured":"Kumar, R., Rubinfeld, R.: Sublinear time algorithms. SIGACT News\u00a034, 57\u201367 (2003)","journal-title":"SIGACT News"},{"issue":"4","key":"48_CR28","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing\u00a015(4), 1036\u20131053 (1986); Earlier version in STOC 1985","journal-title":"SIAM Journal on Computing"},{"key":"48_CR29","doi-asserted-by":"crossref","unstructured":"Luby, M.: Removing randomness in parallel computation without a processor penalty. In: Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 162\u2013173 (1988)","DOI":"10.1109\/SFCS.1988.21934"},{"key":"48_CR30","doi-asserted-by":"crossref","unstructured":"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\u2013165 (2008)","DOI":"10.1109\/FOCS.2008.44"},{"issue":"4","key":"48_CR31","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing\u00a022(4), 838\u2013856 (1993); Earlier version in STOC 1990","journal-title":"SIAM Journal on Computing"},{"key":"48_CR32","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1002\/nme.1620080406","volume":"8","author":"C.P. Neuman","year":"1974","unstructured":"Neuman, C.P., Schonbach, D.I.: Discrete (Legendre) orthogonal polynomials - A survey. International Journal for Numerical Methods in Engineering\u00a08, 743\u2013770 (1974)","journal-title":"International Journal for Numerical Methods in Engineering"},{"key":"48_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-74748-9","volume-title":"Classical Orthogonal Polynomials of a Discrete Variable","author":"A.F. Nikiforov","year":"1991","unstructured":"Nikiforov, A.F., Suslov, S.K., Uvarov, V.B.: Classical Orthogonal Polynomials of a Discrete Variable. Springer, Heidelberg (1991)"},{"key":"48_CR34","doi-asserted-by":"crossref","unstructured":"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\u2013569 (2007)","DOI":"10.1109\/FOCS.2007.4389525"},{"key":"48_CR35","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"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\u2013649. Kluwer Academic Publishers, Dordrecht (2001)"},{"key":"48_CR36","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing\u00a025, 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"48_CR37","doi-asserted-by":"publisher","first-page":"460","DOI":"10.2307\/3620776","volume":"84","author":"J.R. Silvester","year":"2000","unstructured":"Silvester, J.R.: Determinants of block matrices. Maths Gazette\u00a084, 460\u2013467 (2000)","journal-title":"Maths Gazette"},{"key":"48_CR38","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1098\/rstl.1861.0016","volume":"151","author":"H.J.S. Smith","year":"1861","unstructured":"Smith, H.J.S.: On systems of linear indeterminate equations and congruences. Phil. Trans. Royal Soc. London A\u00a0151, 293\u2013326 (1861)","journal-title":"Phil. Trans. Royal Soc. London A"},{"key":"48_CR39","unstructured":"\u0160tefankovi\u010d, D.: Fourier transform in computer science. Master\u2019s thesis, University of Chicago (2000)"},{"key":"48_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626265","volume-title":"Fourier Analysis on Finite Groups and Applications","author":"A. Terras","year":"1999","unstructured":"Terras, A.: Fourier Analysis on Finite Groups and Applications. Cambridge University Press, Cambridge (1999)"},{"issue":"1","key":"48_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S. Yekhanin","year":"2008","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. Journal of the ACM\u00a055(1), 1\u201316 (2008)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T19:30:28Z","timestamp":1635622228000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_48"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}