{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:21:05Z","timestamp":1737091265139,"version":"3.33.0"},"reference-count":12,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4485,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that if<jats:italic>f<\/jats:italic>can be represented in<jats:italic>k<\/jats:italic>\u2010DNF form and in<jats:italic>j<\/jats:italic>\u2010CNF form, then<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log(min(<jats:italic>k, j<\/jats:italic>)\/<jats:italic>q<\/jats:italic>)) queries suffice to compute<jats:italic>f<\/jats:italic>with error probability less than<jats:italic>q<\/jats:italic>, where<jats:italic>n<\/jats:italic>is the number of input bits. \u00a9 1994 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050306","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:47:17Z","timestamp":1180205237000},"page":"453-464","source":"Crossref","is-referenced-by-count":8,"title":["On boolean decision trees with faulty nodes"],"prefix":"10.1002","volume":"5","author":[{"given":"Claire","family":"Kenyon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"U.Feige D.Peleg P.Raghavan andE.Upfal Computing with noisy information 22ndAnnual ACM Symposium on Theory of Computing 1990 pp.128\u2013137.","DOI":"10.1007\/3-540-52921-7_62"},{"volume-title":"An Introduction to Probability Theory and its Applications","year":"1957","author":"Feller W.","key":"e_1_2_1_3_2"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"A.Gal Lower bounds for the complexity for reliable Boolean circuits with noisy gates FOCS'91 pp.594\u2013601.","DOI":"10.1109\/SFCS.1991.185424"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054190000023"},{"volume-title":"The Art of Computer Programming, Vol. I: Fundamental Algorithms","year":"1968","author":"Knuth D. E.","key":"e_1_2_1_6_2"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90559-2"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"N.Nisan CREW PRAMs and decision trees STOC'89 pp.327\u2013335.","DOI":"10.1145\/73007.73038"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90077-7"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"N.Pippenger On networks of noisy gates FOCS'85 pp.30\u201338.","DOI":"10.1109\/SFCS.1985.41"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"R.ReischukandB.Schmeltz Reliable computation with noisy circuits and decistion trees\u2014A generalnlognlower bound FOCS'91 pp.602\u2013611.","DOI":"10.1109\/SFCS.1991.185425"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"J.Von Neumann Probabilistic logics and the synthesis of reliable organisms from unreliable components inAutomata Studies 43\u201398 Princeton University Press Princeton NJ 1956.","DOI":"10.1515\/9781400882618-003"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:21:30Z","timestamp":1737051690000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,7]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,7]]}},"alternative-id":["10.1002\/rsa.3240050306"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050306","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"type":"print","value":"1042-9832"},{"type":"electronic","value":"1098-2418"}],"subject":[],"published":{"date-parts":[[1994,7]]}}}