{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:57:54Z","timestamp":1770753474721,"version":"3.50.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319066851","type":"print"},{"value":"9783319066868","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_8","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"97-110","source":"Crossref","is-referenced-by-count":4,"title":["Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees"],"prefix":"10.1007","author":[{"given":"Abhishek","family":"Bhrushundi","sequence":"first","affiliation":[]},{"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[]},{"given":"Raghav","family":"Kulkarni","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/060667177","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: It\u2019s all about regularity. SIAM J. Comput.\u00a039(1), 143\u2013167 (2009)","journal-title":"SIAM J. Comput."},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-45198-3_17","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Alon","year":"2003","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S.N., Ron, D.: Testing low-degree polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX 2003 + RANDOM 2003. LNCS, vol.\u00a02764, pp. 188\u2013199. Springer, Heidelberg (2003)"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1145\/2488608.2488662","volume-title":"Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC 2013","author":"A. Bhattacharyya","year":"2013","unstructured":"Bhattacharyya, A., Fischer, E., Hatami, H., Hatami, P., Lovett, S.: Every locally characterized affine-invariant property is testable. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC 2013, pp. 429\u2013436. ACM Press, New York (2013), \n                  \n                    http:\/\/doi.acm.org\/10.1145\/2488608.2488662"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 478\u2013487 (2010)","DOI":"10.1109\/FOCS.2010.53"},{"key":"8_CR5","first-page":"89","volume":"20","author":"A. Bhrushundi","year":"2013","unstructured":"Bhrushundi, A.: On testing bent functions. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 89 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"8_CR6","first-page":"142","volume":"20","author":"A. Bhrushundi","year":"2013","unstructured":"Bhrushundi, A., Chakraborty, S., Kulkarni, R.: Property testing bounds for linear and quadratic functions via parity decision trees. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 142 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"8_CR7","first-page":"151","volume-title":"Proc. ACM Symposium on the Theory of Computing","author":"E. Blais","year":"2009","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc. ACM Symposium on the Theory of Computing, pp. 151\u2013158. ACM, New York (2009)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing via communication complexity. In: Proc. CCC (2011)","DOI":"10.1109\/CCC.2011.31"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/978-3-642-32512-0_37","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Blais","year":"2012","unstructured":"Blais, E., Kane, D.: Tight bounds for testing k-linearity. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 435\u2013446. Springer, Heidelberg (2012)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Blais, E., Weinstein, A., Yoshida, Y.: Partially symmetric functions are efficiently isomorphism-testable. In: FOCS, pp. 551\u2013560 (2012)","DOI":"10.1109\/FOCS.2012.53"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. In: STOC, pp. 73\u201383 (1990)","DOI":"10.1145\/100216.100225"},{"key":"8_CR12","unstructured":"Buhrman, H., Garc\u00eda-Soriano, D., Matsliah, A., de Wolf, R.: The non-adaptive query complexity of testing k-parities. CoRR abs\/1209.3849 (2012)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Seshadhri, C.: A o(n) monotonicity tester for boolean functions over the hypercube. CoRR abs\/1302.4536 (2013)","DOI":"10.1145\/2488608.2488660"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Fischer, E., Garc\u00eda-Soriano, D., Matsliah, A.: Junto-symmetric functions, hypergraph isomorphism and crunching. In: IEEE Conference on Computational Complexity, pp. 148\u2013158 (2012)","DOI":"10.1109\/CCC.2012.28"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Chen, V., Sudan, M., Xie, N.: Property testing via set-theoretic operations. In: ICS, pp. 211\u2013222 (2011)","DOI":"10.1007\/978-3-642-16367-8_12"},{"key":"8_CR16","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Science\u00a075, 97\u2013126 (2001)","journal-title":"Science"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. Journal of Computer and System Sciences\u00a068(4), 753\u2013787 (2004), Special Issue on FOCS 2002","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On testing computability by small width obdds. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol.\u00a06302, pp. 574\u2013587. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15369-3_43"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-642-40328-6_39","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Grigorescu","year":"2013","unstructured":"Grigorescu, E., Wimmer, K., Xie, N.: Tight lower bounds for testing linear isomorphism. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 559\u2013574. Springer, Heidelberg (2013)"},{"issue":"4","key":"8_CR21","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.ipl.2006.01.014","volume":"99","author":"W. Huang","year":"2006","unstructured":"Huang, W., Shi, Y., Zhang, S., Zhu, Y.: The communication complexity of the hamming distance problem. Inf. Process. Lett.\u00a099(4), 149\u2013153 (2006)","journal-title":"Inf. Process. Lett."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: STOC, pp. 403\u2013412 (2008)","DOI":"10.1145\/1374376.1374434"},{"issue":"4","key":"8_CR23","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T. Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science\u00a03(4), 263\u2013398 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"8_CR24","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes (North-Holland Mathematical Library). North Holland Publishing Co. (June 1988), \n                  \n                    http:\/\/www.worldcat.org\/isbn\/0444851933"},{"key":"8_CR25","unstructured":"Neumann, T.: Bent functions, Master\u2019s thesis (2006)"},{"key":"8_CR26","unstructured":"O\u2019Donnell, R.: Analysis of boolean functions (2012), \n                  \n                    http:\/\/www.analysisofbooleanfunctions.org"},{"issue":"3","key":"8_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0097-3165(76)90024-8","volume":"20","author":"O. Rothaus","year":"1976","unstructured":"Rothaus, O.: On bent functions. Journal of Combinatorial Theory, Series A\u00a020(3), 300\u2013305 (1976), \n                  \n                    http:\/\/www.sciencedirect.com\/science\/article\/pii\/0097316576900248","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"8_CR28","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. Electronic Colloquium on Computational Complexity (ECCC)\u00a011(013) (2011)"},{"key":"8_CR29","unstructured":"Sun, X., Wang, C.: Randomized communication complexity for linear algebra problems over finite fields. In: STACS, pp. 477\u2013488 (2012)"},{"key":"8_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/978-3-642-39206-1_71","volume-title":"Automata, Languages, and Programming","author":"K. Wimmer","year":"2013","unstructured":"Wimmer, K., Yoshida, Y.: Testing linear-invariant function isomorphism. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 840\u2013850. Springer, Heidelberg (2013)"},{"issue":"26-28","key":"8_CR31","doi-asserted-by":"publisher","first-page":"2612","DOI":"10.1016\/j.tcs.2010.03.027","volume":"411","author":"Z. Zhang","year":"2010","unstructured":"Zhang, Z., Shi, Y.: On the parity complexity measures of boolean functions. Theor. Comput. Sci.\u00a0411(26-28), 2612\u20132618 (2010)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T19:52:43Z","timestamp":1558900363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}