{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:48:11Z","timestamp":1793850491652,"version":"4.6.1"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1994,10]]},"abstract":"<jats:p>This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems.<\/jats:p>","DOI":"10.1137\/s0097539791195877","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:39:46Z","timestamp":1109227186000},"page":"1001-1018","source":"Crossref","is-referenced-by-count":157,"title":["Computing with Noisy Information"],"prefix":"10.1137","volume":"23","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eli","family":"Upfal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89546"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90102-2"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. Hastad, F. T. Leighton, M. Newman,  Reconfiguring a hypercube in the presence of faults,  19th Annual Symposium on Theory of Computing,  1987,  274\u2013284","DOI":"10.1145\/28395.28425"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R9","unstructured":"R. M. Karp,  1989, Personal communication, Berkeley, CA"},{"key":"R10","unstructured":"C. Kenyon, V. King,  On Boolean decision trees with faulty nodes,  Proc. of the Israel Symposium on the Theory of Computing and Systems, Springer-Verlag, New York,  1992"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054190000023"},{"key":"R12","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90077-7"},{"key":"R15","unstructured":"A. Pelc,  Sorting with random errors, Technical Report, TR # RR 89\/06-12, Univ. du Quebec a Hull, Quebec, Canada,  1989"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"N. Pippenger,  On networks of noisy gates,  26th Annual Symposium on Foundations of Computer Science,  1985,  30\u201338","DOI":"10.1109\/SFCS.1985.41"},{"key":"R17","unstructured":"N. Pippenger, G. D. Stamoulis, J. N. Tsitsiklis,  On a lower bound for the redundancy of reliable networks with noisy gates, IEEE Transactions on Information Theory, to appear"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"B. Ravikumar, K. Ganesan, K. B. Lakshmanan,  On selecting the largest element in spite of erroneous information,  Proc. 4th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci., Springer-Verlag, New York,  1987,  88\u201399 0634.68065","DOI":"10.1007\/BFb0039597"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90104-X"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0214030"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185425"},{"key":"R22","first-page":"631","volume-title":"Selected Papers of Alfred Renyi","volume":"2","author":"Renyi A.","year":"1976"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Saks, A. Wigderson,  Probabilistic Boolean decision trees and the complexity of evaluating game trees,  27th Annual Symposium on Foundations of Computer Science, Toronto, Ontario,  1986,  29\u201338","DOI":"10.1109\/SFCS.1986.44"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1971.1054625"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0214009"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539791195877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:12Z","timestamp":1787337792000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539791195877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,10]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1994,10]]}},"alternative-id":["10.1137\/S0097539791195877"],"URL":"https:\/\/doi.org\/10.1137\/s0097539791195877","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,10]]}}}