The noisy broadcast model was first studied in [Gallager, TranInf'88] where an @math -character input is distributed among @math processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability @math . [Gallager, TranInf'88] gave an algorithm for all processors to learn the input in @math rounds with high probability. Later, a matching lower bound of @math was given in [Goyal, Kindler, Saks; SICOMP'08]. We study a relaxed version of this model where each reception is erased and replaced with a ?' independently with probability @math . In this relaxed model, we break past the lower bound of [Goyal, Kindler, Saks; SICOMP'08] and obtain an @math -round algorithm for all processors to learn the input with high probability. We also show an @math -round algorithm for the same problem when the alphabet size is @math .
This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems. A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(lnN)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication. > We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the @math workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., Springer-Verlag, New York, 1987, pp. 60-62]. In this model there are @math processors @math , each of which is initially given a private input bit @math . The goal is for @math to learn the value of @math , for some specified function @math , using a series of noisy broadcasts. At each step a designated processor broadcasts one bit to all of the other processors, and the bit received by each processor is flipped with fixed probability (independently for each recipient). In 1988, Gallager [IEEE Trans. Inform. Theory, 34 (1988), pp. 176-180] gave a noise-resistant protocol that allows @math to learn the entire input with constant probability in @math broadcasts. We prove that Gallager's protocol is optimal, up to a constant factor. Our lower bound follows by reduction from a lower bound for generalized noisy decision trees, a new model which may be of independent interest. For this new model we show a lower bound of @math on the depth of a tree that learns the entire input. While the above lower bound is for an @math -bit function, we also show an @math lower bound for the number of broadcasts required to compute certain explicit boolean-valued functions, when the correct output must be attained with probability at least @math for a constant parameter @math (this bound applies to all threshold functions as well as any other boolean-valued function with linear sensitivity). This bound also follows by reduction from a lower bound of @math on the depth of generalized noisy decision trees that compute the same functions with the same error. We also show a (nontrivial) @math lower bound on the depth of generalized noisy decision trees that compute such functions with small constant error. Finally, we show the first protocol in the noisy broadcast model that computes the Hamming weight of the input using a linear number of broadcasts.