{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:49Z","timestamp":1759638889861},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_37","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"435-446","source":"Crossref","is-referenced-by-count":7,"title":["Tight Bounds for Testing k-Linearity"],"prefix":"10.1007","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Kane","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"37_CR1","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M. Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. IEEE Trans. on Information Theory\u00a042(6), 1781\u20131795 (1996)","journal-title":"IEEE Trans. on Information Theory"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proc. of the 25th Symposium on Theory of Computing, pp. 294\u2013304 (1993)","DOI":"10.1145\/167088.167174"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Sudan, M.: Improved non-approximability results. In: Proc. of the 26th Symposium on Theory of Computing, pp. 184\u2013193 (1994)","DOI":"10.1145\/195058.195129"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. In: Proc. of the 26th Conference on Computational Complexity (2011)","DOI":"10.1109\/CCC.2011.31"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"Blais, E., O\u2019Donnell, R.: Lower bounds for testing function isomorphism. In: Proc. of the 25th Conference on Computational Complexity, pp. 235\u2013246 (2010)","DOI":"10.1109\/CCC.2010.30"},{"key":"37_CR7","doi-asserted-by":"publisher","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. J. Comput. Syst. Sci.\u00a047, 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Garc\u00eda-Soriano, D., Matsliah, A.: Nearly tight bounds for testing function isomorphism. In: Proc. 22nd Symposium on Discrete Algorithms, pp. 1683\u20131702 (2011)","DOI":"10.1137\/1.9781611973082.130"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H.K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R.A., Wan, A.: Testing for concise representations. In: Proc. 48th Symposium on Foundations of Computer Science, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.4389524"},{"key":"37_CR10","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions. Bulletin of the EATCS\u00a075, 97\u2013126 (2001)","journal-title":"Bulletin of the EATCS"},{"issue":"4","key":"37_CR11","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. J. Comput. Syst. Sci.\u00a068(4), 753\u2013787 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/978-3-642-15369-3_43","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"O. Goldreich","year":"2010","unstructured":"Goldreich, O.: On Testing Computability by Small Width OBDDs. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010, LNCS, vol.\u00a06302, pp. 574\u2013587. Springer, Heidelberg (2010)"},{"key":"37_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Property Testing","year":"2010","unstructured":"Goldreich, O. (ed.): Property Testing. LNCS, vol.\u00a06390. Springer, Heidelberg (2010)"},{"issue":"4","key":"37_CR14","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. of the ACM"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1137\/080715548","volume":"39","author":"T. Kaufman","year":"2010","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the \u03b5-soundness bound of the linearity test over GF(2). SIAM J. on Computing\u00a039, 1988\u20132003 (2010)","journal-title":"SIAM J. on Computing"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: Proc. STOC 1992, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1561\/2200000004","volume":"1","author":"D. Ron","year":"2008","unstructured":"Ron, D.: Property testing: A learning theory perspective. Found. Trends Mach. Learn.\u00a01, 307\u2013402 (2008)","journal-title":"Found. Trends Mach. Learn."},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci.\u00a05, 73\u2013205 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"37_CR19","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. Technical Report TR11-013, ECCC (2011)"},{"issue":"2","key":"37_CR20","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 J. Comput.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"37_CR21","unstructured":"Szeg\u0151, G.: Orthogonal Polynomials, 4th edn. Colloquium Publications, vol.\u00a023. AMS (1975)"},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"Van Lint, J.H.V.: Introduction to Coding Theory, 3rd edn. Graduate Texts in Mathematics, vol.\u00a086. Springer (1999)","DOI":"10.1007\/978-3-642-58575-3"},{"key":"37_CR23","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: towards a unified measure of complexity. In: Proc. 18th Sym. on Foundations of Comput. Sci., pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:05:32Z","timestamp":1620129932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}