Computing with Noisy Information
- 1 October 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (5), 1001-1018
- https://doi.org/10.1137/s0097539791195877
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Fault tolerant sorting networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the complexity of finite random functionsInformation Processing Letters, 1992
- ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTSInternational Journal of Foundations of Computer Science, 1990
- Searching with known error probabilityTheoretical Computer Science, 1989
- Parallel Merge SortSIAM Journal on Computing, 1988
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- Sorting inc logn parallel stepsCombinatorica, 1983
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952