Theory of Computing
-------------------
Title : Rounds vs. Queries Tradeoff in Noisy Computation
Authors : Navin Goyal and Michael Saks
Volume : 6
Number : 6
Pages : 113-134
URL : http://www.theoryofcomputing.org/articles/v006a006
Abstract
--------
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.