{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:25:13Z","timestamp":1747866313483,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_27","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"317-329","source":"Crossref","is-referenced-by-count":5,"title":["Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority"],"prefix":"10.1007","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Magniez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashwin","family":"Nayak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Blum, M., Impagliazzo, R.: General oracle and oracle classes. In: Proc. FOCS 1987, pp. 118\u2013126 (1987)","DOI":"10.1109\/SFCS.1987.30"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Hemachandra, L.: One-way functions, robustness, and non-isomorphism of NP-complete sets. In: Proc. Struc. in Complexity Th. 1987, pp. 160\u2013173 (1987)","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Heiman, R., Newman, I., Wigderson, A.: On read-once threshold formulae and their randomized decision tree complexity. In: Proc. Struc. in Complexity Th. 1990, pp. 78\u201387 (1990)","DOI":"10.1109\/SCT.1990.113956"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Heiman, R., Wigderson, A.: Randomized versus deterministic decision tree complexity for read-once boolean functions. In: Proc. Struc. in Complexity Th. 1991, pp. 172\u2013179 (1991)","DOI":"10.1007\/BF01212962"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Jayram, T., Kumar, R., Sivakumar, D.: Two applications of information complexity. In: Proc. STOC 2003, pp. 673\u2013682 (2003)","DOI":"10.1145\/780542.780640"},{"key":"27_CR6","unstructured":"Landau, I., Nachmias, A., Peres, Y., Vanniasegaram, S.: The lower bound for evaluating a recursive ternary majority function: an entropy-free proof. Tech. rep., Dep. of Stat., UC Berkeley (2006) (undergraduate Research Report), http:\/\/www.stat.berkeley.edu\/110"},{"key":"27_CR7","first-page":"327","volume-title":"Proc. STOC 1989","author":"N. Nisan","year":"1989","unstructured":"Nisan, N.: CREW PRAMs and decision trees. In: Proc. STOC 1989, pp. 327\u2013335. ACM, New York (1989)"},{"key":"27_CR8","first-page":"103","volume-title":"Proc. 40th STOC","author":"B.W. Reichardt","year":"2008","unstructured":"Reichardt, B.W., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proc. 40th STOC, pp. 103\u2013112. ACM, New York (2008)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proc. FOCS 1986, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"issue":"1","key":"27_CR10","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 boolean decision tree complexity of read-once formulae. Random Structures and Algorithms\u00a06(1), 75\u201387 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"27_CR11","first-page":"385","volume":"9","author":"M. Snir","year":"1990","unstructured":"Snir, M.: Lower bounds for probabilistic linear decision trees. Combinatorica\u00a09, 385\u2013392 (1990)","journal-title":"Combinatorica"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G. Tardos","year":"1990","unstructured":"Tardos, G.: Query complexity or why is it difficult to separate NP A \u2009\u2229\u2009coNP A from P A by a random oracle. Combinatorica\u00a09, 385\u2013392 (1990)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T11:29:02Z","timestamp":1741260542000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}