{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:14:07Z","timestamp":1787321647199,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1995,2]]},"abstract":"<jats:p>The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the gaffs between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. An interesting connection of this model to the complexity of resolution proofs is also mentioned.<\/jats:p>","DOI":"10.1137\/s0895480192233867","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:06:23Z","timestamp":1109145983000},"page":"119-132","source":"Crossref","is-referenced-by-count":34,"title":["Search Problems in the Decision Tree Model"],"prefix":"10.1137","volume":"8","author":[{"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl, J. Simon, Complexity classes in communication complexity theory, Proc. 27th Annual IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, 1986, 337\u20133470825.73466","DOI":"10.1109\/SFCS.1986.15"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Blum, R. Impagliazzo, Generic oracles and oracles classes, Proc. 28th Annual IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, 1987, 118\u2013126","DOI":"10.1109\/SFCS.1987.30"},{"key":"R3","unstructured":"A. Blake, Ph.D. Thesis, Canonical expressions in Boolean algebra, Department of Mathematics, Chicago University, Chicago, 1937"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"R5","unstructured":"E. Szemer\u00e9di, 1991, Personal communication"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, L. A. Hemachandra, One-way functions, robustness and the non-isomorphism of NP-complete sets, Proc. 2nd Structure in Complexity Theory Conference, IEEE Computer Society Press, 1987, 160\u2013173","DOI":"10.1109\/PSCT.1987.10319267"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89568"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Naor, Decision trees downward closure, Proc. 3rd Structure in Complexity Theory Conference, IEEE Computer Society Press, 1988, 29\u201338","DOI":"10.1109\/SCT.1988.5260"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Karchmer, A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proc. 20th Annual ACM Symp. on Theory of Computing, 1988, 539\u2013550","DOI":"10.1145\/62212.62265"},{"key":"R12","unstructured":"F. Thomson Leighton, Introduction to parallel algorithms and architectures, Morgan Kaufmann, San Mateo, CA, 1992, 439\u2013510, Arrays, Trees, Hypercubes92j:680410743.68007"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Lubotzky, R. Phillips, P. Sarnak, Explicit expanders and the Ramanujan conjecture, Proc. 18th Annual ACM Symp. on Theory of Computing, ACM Press, 1986, 240\u2013246","DOI":"10.1145\/12130.12154"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"N. Nisan, CREW PRAMS and decision trees, Proc. 21st ACM Symp. on Theory of Computing, ACM Press, 1989, 327\u2013335","DOI":"10.1145\/73007.73038"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, Graph theoretic lemmata and complexity classes, Proc. 31st IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, 1990, 794\u2013801","DOI":"10.1109\/FSCS.1990.89602"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50020-5"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"R. Raz, A. Wigderson, Monotone circuits for matching require linear depth, Proc. 22th ACM Symp. on Theory of Computing, ACM Press, 1990, 287\u2013292","DOI":"10.1145\/100216.100253"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Probabilistic computations: toward a unified measure of complexity (extended abstract), 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977), IEEE Comput. Sci., Long Beach, Calif., 1977, 222\u201322758:8500","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480192233867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:13:46Z","timestamp":1787318026000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480192233867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["10.1137\/S0895480192233867"],"URL":"https:\/\/doi.org\/10.1137\/s0895480192233867","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}