摘要：We show that a noisy parallel decision tree making queries needs log rounds to compute OR of bits. This answers a question of Newman [ IEEE Conference on Computational Complexity , 2004, 113--124]. We prove more general tradeoffs between the number of queries and rounds. We also settle a similar question for computing MAX in the noisy comparison tree model; these results bring out interesting differences among the noise models.
