pdf icon
Volume 6 (2010) Article 6 pp. 113-134
Rounds vs. Queries Tradeoff in Noisy Computation
Received: January 26, 2010
Published: September 2, 2010
Download article from ToC site:
[PDF (294K)] [PS (970K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: complexity theory, decision trees, noisy computation
Categories: complexity theory, decision tree, noisy computation, lower bounds
ACM Classification: F.2.3
AMS Classification: 68Q13

Abstract: [Plain Text Version]

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 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.