Volume 6 (2010)
Article 6 pp. 113-134
Rounds vs. Queries Tradeoff in Noisy Computation
Received: January 26, 2010
Published: September 2, 2010
Published: September 2, 2010
Keywords: complexity theory, decision trees, noisy computation
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.