{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:38Z","timestamp":1759063538621},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1991,12,1]],"date-time":"1991-12-01T00:00:00Z","timestamp":691545600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,12]]},"DOI":"10.1007\/bf01212962","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T13:00:21Z","timestamp":1109336421000},"page":"311-329","source":"Crossref","is-referenced-by-count":14,"title":["Randomized vs. deterministic decision tree complexity for read-once Boolean functions"],"prefix":"10.1007","volume":"1","author":[{"given":"Rafi","family":"Heiman","sequence":"first","affiliation":[]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"D. Angluin, L. Hellerstein, and M. Karpinski. Learning read once formulae with queries. Technical Report UCB CSD 89-528, U.C. Berkeley, 1989. To appear in J. Assoc. Comput. Mach."},{"key":"CR2","unstructured":"R. B. Boppana. Amplification of probabilistic Boolean formulae, volume 5 ofAdvances in Computer Research, editor S. Micali, pages 27?45, JAI press, 1989."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"P. Hajnal. On the power of randomness in the decision tree model. InProc. 5th Structure in Complexity Theory Conf., pages 66?77, 1990.","DOI":"10.1109\/SCT.1990.113955"},{"key":"CR4","volume-title":"Randomized Decision Tree Complexity for Read-Once Boolean Functions","author":"R. Heiman","year":"1991","unstructured":"R. Heiman.Randomized Decision Tree Complexity for Read-Once Boolean Functions. PhD thesis, submitted to The Feinberg Graduate School, The Weizmann Institute of Science, Rehovot 76100, Israel, 1991."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"R. Heiman, I. Newman, and A. Wigderson. On read-once threshold formulae and their randomized decision tree complexity. InProc. 5th Structure in Complexity Theory Conf., pages 78?87, 1990. To appear in Theoretical Computer Science.","DOI":"10.1109\/SCT.1990.113956"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"V. King. Lower bounds on the complexity of graph properties. InProc. 20th ACM Symp. on Theory of Computing, pages 468?476, 1988.","DOI":"10.1145\/62212.62258"},{"key":"CR7","first-page":"559","volume":"25","author":"J. Pearl","year":"1982","unstructured":"J. Pearl. The solution for the branching factor of the alpha beta pruning algorithm and its optimality.Comm. Assoc. Comput. Math., 25:559?564, 1982.","journal-title":"Comm. Assoc. Comput. Math."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. InProc. 27th IEEE Symp. on Foundations of Computer Science, pages 29?38, 1986.","DOI":"10.1109\/SFCS.1986.44"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"M. Snir. Lower bounds for probabilistic linear decision trees.Theoretical Computer Science, 38:69?82, 1985.","journal-title":"Theoretical Computer Science"},{"key":"CR10","first-page":"69","volume":"3","author":"M. Tarsi","year":"1983","unstructured":"M. Tarsi. Optimal search on some game trees.J. Assoc. Comput. Mach., 3:69?82, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. Short monotone formulae for the majority function.J. Algorithms, 5:363?366, 1984.","journal-title":"J. Algorithms"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Probabilistic computations: towards a unified measure of complexity. InProc. 18th IEEE Symp. on Foundations of Computer Science, pages 222?227, 1977.","DOI":"10.1109\/SFCS.1977.24"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Lower bounds to randomized algorithms for graph properties. InProc. 28th IEEE Symp. on Foundations of Computer Science, pages 393?400, 1987.","DOI":"10.1109\/SFCS.1987.39"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01212962.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01212962\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01212962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T09:47:12Z","timestamp":1556790432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01212962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,12]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,12]]}},"alternative-id":["BF01212962"],"URL":"https:\/\/doi.org\/10.1007\/bf01212962","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,12]]}}}