COMPUTING WITH NOISY INFORMATION

This paper studies the depth of noisy decision trees in which each nod e gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of q ueries 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 para llel selection and sorting with noisy comparisons, giving tight bounds for several problems.