{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:05Z","timestamp":1725795905461},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_3","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"26-38","source":"Crossref","is-referenced-by-count":0,"title":["Weak Parity"],"prefix":"10.1007","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[]},{"given":"Andris","family":"Ambainis","sequence":"additional","affiliation":[]},{"given":"Kaspars","family":"Balodis","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Bavarian","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Childs, A., Le Gall, F., Tani, S.: The quantum query complexity of certification. Quantum Information and Computation\u00a010(3-4) arXiv:0903.1291 (2010)","DOI":"10.26421\/QIC10.3-4-1"},{"key":"3_CR2","unstructured":"Ambainis, A., Childs, A.M., Reichardt, B.W., \u0160palek, R., Zhang, S.: Any AND-OR formula of size N can be evaluated in time N 1\/2\u2009+\u2009o(1) on a quantum computer. In: Proc. IEEE FOCS (2007); quant-ph\/0703015 and arXiv:0704.3628"},{"key":"#cr-split#-3_CR3.1","doi-asserted-by":"crossref","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM\u00a048(4), 778-797 (2001)","DOI":"10.1145\/502090.502097"},{"key":"#cr-split#-3_CR3.2","unstructured":"Earlier version in IEEE FOCS 1998, pp. 352-361 (1998) quant-ph\/9802049"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput.\u00a026(5), 1510\u20131523 (1997); quant-ph\/9701001","DOI":"10.1137\/S0097539796300933"},{"key":"3_CR5","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. Theoretical Comput. Sci.\u00a0288, 21\u201343 (2002)","journal-title":"Theoretical Comput. Sci."},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/0097-3165(88)90034-9","volume":"49","author":"F.R.K. Chung","year":"1988","unstructured":"Chung, F.R.K., F\u00fcredi, Z., Graham, R.L., Seymour, P.: On induced subgraphs of the cube. J. Comb. Theory Ser. A\u00a049(1), 180\u2013187 (1988)","journal-title":"J. Comb. Theory Ser. A"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. Roy. Soc. London\u00a0A439, 553\u2013558 (1992)","DOI":"10.1098\/rspa.1992.0167"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing\u00a04(1), 169\u2013190 (2008); quant-ph\/0702144","DOI":"10.4086\/toc.2008.v004a008"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: A limit on the speed of quantum computation in determining parity. Phys. Rev. Lett.\u00a081, 5442\u20135444 (1998); quant-ph\/9802045","DOI":"10.1103\/PhysRevLett.81.5442"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0097-3165(92)90060-8","volume":"61","author":"C. Gotsman","year":"1992","unstructured":"Gotsman, C., Linial, N.: The equivalence of two problems on the cube. J. Comb. Theory Ser. A\u00a061(1), 142\u2013146 (1992)","journal-title":"J. Comb. Theory Ser. A"},{"key":"3_CR11","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theory of Computing Library Graduate Surveys\u00a04 (2011)"},{"key":"3_CR12","unstructured":"Midrijanis, G.: On randomized and quantum query complexities (2005) quant-ph\/0501142"},{"issue":"6","key":"3_CR13","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N. Nisan","year":"1991","unstructured":"Nisan, N.: CREW PRAMs and decision trees. SIAM J. Comput.\u00a020(6), 999\u20131007 (1991)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_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(4), 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In: Proc. IEEE FOCS, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"issue":"1","key":"3_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/rsa.3240060108","volume":"6","author":"M. Santha","year":"1995","unstructured":"Santha, M.: On the Monte-Carlo decision tree complexity of read-once formulae. Random Structures and Algorithms\u00a06(1), 75\u201387 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Tal, A.: Properties and applications of Boolean function composition. In: Proc. Innovations in Theoretical Computer Science (ITCS), pp. 441\u2013454 (2013); ECCC TR12-163","DOI":"10.1145\/2422436.2422485"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T06:06:14Z","timestamp":1689314774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}