{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:48Z","timestamp":1763467788183,"version":"3.33.0"},"reference-count":13,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4301,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1995,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. We prove for a large class of read\u2010once formulae that this trivial speed\u2010up is the best that a Monte Carlo algorithm can achieve. For every formula<jats:italic>F<\/jats:italic>belonging to that class we show that the Monte Carlo complexity of<jats:italic>F<\/jats:italic>with two\u2010sided error<jats:italic>p<\/jats:italic>is (1 \u2212 2<jats:italic>p<\/jats:italic>)<jats:italic>R<\/jats:italic>(<jats:italic>F<\/jats:italic>), and with one\u2010sided error<jats:italic>p<\/jats:italic>is (1 \u2212<jats:italic>p<\/jats:italic>)<jats:italic>R<\/jats:italic>(<jats:italic>F<\/jats:italic>), where<jats:italic>R<\/jats:italic>(<jats:italic>F<\/jats:italic>) denotes the Las Vegas complexity of<jats:italic>F<\/jats:italic>. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analogous to the lower bound due to Saks and Wigderson on their Las Vegas complexity.<\/jats:p>","DOI":"10.1002\/rsa.3240060108","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:52:51Z","timestamp":1180205571000},"page":"75-87","source":"Crossref","is-referenced-by-count":31,"title":["On the Monte carlo boolean decision tree complexity of read\u2010once formulae"],"prefix":"10.1002","volume":"6","author":[{"given":"Miklos","family":"Santha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"M.BlumandR.Impagliazzo Generic oracles and oracle classes Proc. 18th IEEE FOCS 1987 pp.118\u2013126.","key":"e_1_2_1_2_2","DOI":"10.1109\/SFCS.1987.30"},{"doi-asserted-by":"crossref","unstructured":"P.Hajnal On the power of randomness in the decision tree model Proc. 5th Structure in Complexity Theory 1990 pp.66\u201377.","key":"e_1_2_1_3_2","DOI":"10.1109\/SCT.1990.113955"},{"doi-asserted-by":"crossref","unstructured":"R.Heiman I.Newman andA.Wigderson On read\u2010once threshold formulae and their randomized decision tree complexity Proc. 5th Structure in Complexity Theory 1990 pp.78\u201387.","key":"e_1_2_1_4_2","DOI":"10.1109\/SCT.1990.113956"},{"doi-asserted-by":"crossref","unstructured":"J.HartmanisandL.Hemachandra One\u2010way functions robustness and non\u2010isomorphism ofNP\u2010complete sets Proc. 2nd Structure in Complexity Theory 1987 pp.160\u2013173.","key":"e_1_2_1_5_2","DOI":"10.1109\/PSCT.1987.10319267"},{"unstructured":"R.HeimanandA.Wigderson Randomized versus deterministic decision tree complexity for read\u2010once Boolean functions Proc. 6th IEEE Structure in Complexity Theory 1991 pp.170\u2013179.","key":"e_1_2_1_6_2"},{"doi-asserted-by":"crossref","unstructured":"V.King Lower bound on the complexity of graph properties Proc. 20th ACM STOC 1988 pp.468\u2013476.","key":"e_1_2_1_7_2","DOI":"10.1145\/62212.62258"},{"doi-asserted-by":"crossref","unstructured":"N.Nisan CREW PRAMs and decision trees. Proc. 21st ACM STOC 1989 pp.327\u2013335.","key":"e_1_2_1_8_2","DOI":"10.1145\/73007.73038"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_2","DOI":"10.1016\/0304-3975(76)90053-0"},{"doi-asserted-by":"crossref","unstructured":"M.SaksandA.Wigderson Probabilistic boolean decision trees and the complexity of evaluating game trees Proc. 27th IEEE FOCS 1986 pp.29\u201338.","key":"e_1_2_1_10_2","DOI":"10.1109\/SFCS.1986.44"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_2","DOI":"10.1016\/0304-3975(85)90210-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_2","DOI":"10.1007\/BF02125350"},{"unstructured":"A.Yao Probabilistic computations: towards a unified measure of complexity Proc. 18th IEEE FOCS 197 pp.393\u2013400.","key":"e_1_2_1_13_2"},{"doi-asserted-by":"crossref","unstructured":"A.Yao Lower bounds to randomized algorithms for graph properties Proc. 28th IEEE FOCS 1987 pp.393\u2013400.","key":"e_1_2_1_14_2","DOI":"10.1109\/SFCS.1987.39"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240060108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240060108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:21:35Z","timestamp":1737051695000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240060108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["10.1002\/rsa.3240060108"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240060108","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"type":"print","value":"1042-9832"},{"type":"electronic","value":"1098-2418"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}