{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T04:11:08Z","timestamp":1746072668472,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382352"},{"type":"electronic","value":"9783642382369"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38236-9_21","type":"book-chapter","created":{"date-parts":[[2013,4,15]],"date-time":"2013-04-15T02:38:02Z","timestamp":1365993482000},"page":"224-235","source":"Crossref","is-referenced-by-count":1,"title":["Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive"],"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","reference":[{"key":"21_CR1","unstructured":"Babai, L., Banerjee, A., Kulkarni, R., Naik, V.: Evasiveness and the Distribution of Prime Numbers. In: STACS 2010, pp. 71\u201382 (2010)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Benjamini, I., Kalai, G., Schramm, O.: Noise sensitivity of Boolean functions and its application to percolation. Inst. Hautes tudes Sci. Publ. (MATH), 90 (1999)","DOI":"10.1007\/BF02698830"},{"issue":"1","key":"21_CR3","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.\u00a0288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR4","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/S0097539700382005","volume":"31","author":"A. Chakrabarti","year":"2001","unstructured":"Chakrabarti, A., Khot, S., Shi, Y.: Evasiveness of Subgraph Containment and Related Properties. SIAM J. Comput.\u00a031(3), 866\u2013875 (2001)","journal-title":"SIAM J. Comput."},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1112\/jlms\/s1-26.4.273","volume":"36","author":"C.B. Haselgrove","year":"1951","unstructured":"Haselgrove, C.B.: Some theorems on the analytic theory of numbers. J. London Math. Soc.\u00a036, 273\u2013277 (1951)","journal-title":"J. London Math. Soc."},{"issue":"4","key":"21_CR6","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/s00453-002-0981-6","volume":"34","author":"T.P. Hayes","year":"2002","unstructured":"Hayes, T.P., Kutin, S., van Melkebeek, D.: The Quantum Black-Box Complexity of Majority. Algorithmica\u00a034(4), 480\u2013501 (2002)","journal-title":"Algorithmica"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Kulkarni, R.: Evasiveness Through A Circuit Lens. To appear in ITCS 2013 (2013)","DOI":"10.1145\/2422436.2422454"},{"issue":"4","key":"21_CR8","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\u00a04(4), 297\u2013306 (1984)","journal-title":"Combinatorica"},{"issue":"6","key":"21_CR9","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.\u00a022(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"key":"21_CR10","first-page":"63","volume":"19","author":"R. Kulkarni","year":"2012","unstructured":"Kulkarni, R., Santha, M.: Query complexity of matroids. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 63 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"3","key":"21_CR11","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\u00a040(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"issue":"1","key":"21_CR12","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jctb.2000.2000","volume":"81","author":"F.H. Lutz","year":"2001","unstructured":"Lutz, F.H.: Some Results Related to the Evasiveness Conjecture. Comb. Theory, Ser. B\u00a081(1), 110\u2013124 (2001)","journal-title":"Comb. Theory, Ser. B"},{"key":"21_CR13","unstructured":"Montanaro, A., Osborne, T.: On the communication complexity of XOR functions. CoRR abs\/0909.3392 (2009)"},{"key":"21_CR14","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. Computational Complexity\u00a04, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"issue":"4","key":"21_CR15","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\u00a015(4), 557\u2013565 (1995)","journal-title":"Combinatorica"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02565743","volume":"50","author":"R. Oliver","year":"1975","unstructured":"Oliver, R.: Fixed-point sets of group actions on finite acyclic complexes. Comment. Math. Helv.\u00a050, 155\u2013177 (1975)","journal-title":"Comment. Math. Helv."},{"key":"21_CR17","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 2005, pp. 31\u201339 (2005)","DOI":"10.1109\/SFCS.2005.34"},{"issue":"3","key":"21_CR18","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0304-3975(76)90053-0","volume":"3","author":"R.L. Rivest","year":"1976","unstructured":"Rivest, R.L., Vuillemin, J.: On Recognizing Graph Properties from Adjacency Matrices. Theor. Comput. Sci.\u00a03(3), 371\u2013384 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Robinson, D.J.S.: A Course in the Theory of Groups, 2nd edn. Springer (1996)","DOI":"10.1007\/978-1-4419-8594-1"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Saks, M.E., Wigderson, A.: Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. In: FOCS 1986, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"key":"21_CR21","unstructured":"Shi, Y., Zhang, Z.: Communication Complexities of XOR functions. CoRR abs\/0808.1762 (2008)"},{"issue":"26-28","key":"21_CR22","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."},{"key":"21_CR23","unstructured":"Vinogradov, I.M.: The Method of Trigonometrical Sums in the Theory of Numbers. Trav. Inst. Math. Stekloff 10 (1937) (Russian)"},{"issue":"3","key":"21_CR24","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/0217031","volume":"17","author":"A.C.-C. Yao","year":"1988","unstructured":"Yao, A.C.-C.: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput.\u00a017(3), 517\u2013520 (1988)","journal-title":"SIAM J. Comput."}],"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-642-38236-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:41:02Z","timestamp":1745988062000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38236-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382352","9783642382369"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38236-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}