{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T16:10:06Z","timestamp":1747930206766,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319171418"},{"type":"electronic","value":"9783319171425"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-17142-5_10","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T11:19:29Z","timestamp":1429096769000},"page":"99-109","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Power of Parity Queries in Boolean Decision Trees"],"prefix":"10.1007","author":[{"given":"Raghav","family":"Kulkarni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youming","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"10_CR1","unstructured":"Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. In: ICS 2011, pp. 338\u2013352 (2011)"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-642-32512-0_29","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"A Ada","year":"2012","unstructured":"Ada, A., Fawzi, O., Hatami, H.: Spectral norm of symmetric functions. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol. 7408, pp. 338\u2013349. Springer, Heidelberg (2012)"},{"key":"10_CR3","unstructured":"Babai, L., Banerjee, A., Kulkarni, R., Naik, V.: Evasiveness and the distribution of prime numbers. In: STACS 2010, pp. 71-82 (2010)"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-319-06686-8_8","volume-title":"Computer Science - Theory and Applications","author":"A Bhrushundi","year":"2014","unstructured":"Bhrushundi, A., Chakraborty, S., Kulkarni, R.: Property testing bounds for linear and quadratic functions via parity decision trees. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.\u00c9., Vereshchagin, N.K. (eds.) CSR 2014. LNCS, vol. 8476, pp. 97\u2013110. Springer, Heidelberg (2014). Electronic colloquium on Computational Complexity (ECCC)"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF02698830","volume":"90","author":"I Benjamini","year":"1999","unstructured":"Benjamini, I., Kalai, G., Schramm, O.: Noise sensitivity of boolean functions and its application to percolation. Inst. Hautes Etudes Sci. Publ. Math. 90, 5\u201343 (1999)","journal-title":"Inst. Hautes Etudes Sci. Publ. Math."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Ben- Or, M., Linial, N.: Collective coin flipping. In: Proceedings of the 26th FOCS, pp. 408\u2013416 (1985)","DOI":"10.1109\/SFCS.1985.15"},{"key":"10_CR7","volume-title":"Combinatorics: Set Systems, Hypergraphs, Families Of Vectors And Combinatorial Probability","author":"B Bollobas","year":"1986","unstructured":"Bollobas, B.: Combinatorics: Set Systems, Hypergraphs, Families Of Vectors And Combinatorial Probability. Cambridge University Press, New York (1986)"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1214\/aos\/1176345462","volume":"9","author":"B Efron","year":"1981","unstructured":"Efron, B., Stein, C.: The jackknife estimate of variance. Ann. Stat. 9, 586\u2013596 (1981)","journal-title":"Ann. Stat."},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-642-02927-1_42","volume-title":"Automata, Languages and Programming","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P., O\u2019Donnell, R., Servedio, R.A., Shpilka, A., Wimmer, K.: Testing fourier dimensionality and sparsity. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 500\u2013512. Springer, Heidelberg (2009)"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/s00453-002-0981-6","volume":"34","author":"TP Hayes","year":"2002","unstructured":"Hayes, T.P., Kutin, S., van Melkebeek, D.: The quantum black-box complexity of majority. algorithmica 34(4), 480\u2013501 (2002)","journal-title":"algorithmica"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.gs.2011.004","volume":"2","author":"P Hatami","year":"2011","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theor. Comput. Grad. Surv. 2, 1\u201327 (2011)","journal-title":"Theor. Comput. Grad. Surv."},{"issue":"1","key":"10_CR13","doi-asserted-by":"publisher","first-page":"147","DOI":"10.4086\/toc.2011.v007a010","volume":"7","author":"R Jain","year":"2011","unstructured":"Jain, R., Zhang, S.: The influence lower bound via query elimination. Theor. Comput. 7(1), 147\u2013153 (2011)","journal-title":"Theor. Comput."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Kulkarni, R.: Evasiveness through a circuit lens. In: ITCS 2013 pp. 139\u2013144 (2013)","DOI":"10.1145\/2422436.2422454"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/2527748.2527763","volume":"44","author":"R Kulkarni","year":"2013","unstructured":"Kulkarni, R.: Gems in decision tree complexity revisited. SIGACT News 44(3), 42\u201355 (2013)","journal-title":"SIGACT News"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions (extended abstract). In: FOCS 1988, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"issue":"6","key":"10_CR17","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. SIAM J. Comput. 22(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-642-38233-8_25","volume-title":"Algorithms and Complexity","author":"R Kulkarni","year":"2013","unstructured":"Kulkarni, R., Santha, M.: Query complexity of matroids. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 300\u2013311. Springer, Heidelberg (2013)"},{"issue":"4","key":"10_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J Kahn","year":"1984","unstructured":"Kahn, J., Saks, M.E., Sturtevant, D.: A topological approach to evasiveness. Combinatorica 4(4), 297\u2013306 (1984)","journal-title":"Combinatorica"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.4086\/toc.2010.v006a004","volume":"6","author":"HK Lee","year":"2010","unstructured":"Lee, H.K.: Decision trees and influence: an inductive proof of the OSSS inequality. Theor. Comput. 6(1), 81\u201384 (2010)","journal-title":"Theor. Comput."},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform, and learnability. J. ACM 40(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"key":"10_CR22","unstructured":"Lovasz, L., Young, N. E.: Lecture Notes on Evasiveness of Graph Properties arXiv:cs\/020503 (2002)"},{"key":"10_CR23","unstructured":"Montanaro, A., Osborne, T.: On the communication complexity of XOR functions. CoRR abs\/0909.3392 (2009)"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.: Las Vegas is better than determinism in VLSI and distributed computing. In: Proceedings of the 14th STOC, pp. 330\u2013337. ACM Press, New York (1982)","DOI":"10.1145\/800070.802208"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Nisan, N.: CREW PRAMs and decision trees. In: Proceedings of the 21st STOC, pp. 327\u2013335. ACM Press, New York (1989)","DOI":"10.1145\/73007.73038"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Comput. Complex. 4, 301\u2013313 (1994)","journal-title":"Comput. Complex."},{"issue":"4","key":"10_CR27","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"N Nisan","year":"1995","unstructured":"Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica 15(4), 557\u2013565 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"10_CR28","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/060669309","volume":"37","author":"R O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Servedio, R.A.: Learning monotone decision trees in polynomial time. SIAM J. Comput. 37(3), 827\u2013844 (2007)","journal-title":"SIAM J. Comput."},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Saks, M.E., Schramm, O., Servedio, R.A.: Every decision tree has an influential variable. In: FOCS, pp. 31-39 (2005)","DOI":"10.1109\/SFCS.2005.34"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Making polynomials robust to noise. In: STOC 2012, pp. 747\u2013758 (2012)","DOI":"10.1145\/2213977.2214044"},{"key":"10_CR31","unstructured":"Shi, Y., Zhang, Z.: Communication Complexities of XOR functions CoRR abs\/0808.1762 (2008)"},{"key":"10_CR32","unstructured":"Shpilka, A., Tal, A., Volk, B.L.: On the Structure of Boolean Functions with Small Spectral Norm: arXiv:1304.0371"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Saks, M.E., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: FOCS, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"issue":"26\u201328","key":"10_CR34","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. 411(26\u201328), 2612\u20132618 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10_CR35","doi-asserted-by":"publisher","first-page":"1576","DOI":"10.1214\/aop\/1176988612","volume":"22","author":"M Talagrand","year":"1994","unstructured":"Talagrand, M.: On russo\u2019s approximate 0-1 law. Ann. Probab. 22(3), 1576\u20131587 (1994)","journal-title":"Ann. Probab."},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Tsang, H.Y., Wong, C.H., Xie, N., Zhang, S.: Fourier sparsity, spectral norm, and the Log-rank conjecture. CoRR abs\/1304.1245 (2013) FOCS (2014)","DOI":"10.1109\/FOCS.2013.76"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-17142-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T15:33:46Z","timestamp":1747928026000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-17142-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319171418","9783319171425"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-17142-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}