| Rounds vs Queries Trade-off in Noisy Computation (2006) | |||||||||||||||
Abstract | |||||||||||||||
| We show that a noisy parallel decision tree making O(n) queries needs Ω(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 trade-offs 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||