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