Lower Bounds for the Noisy Broadcast Problem

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the 1984workshop 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 n+1processors P_0,P_1,\ldots,P_n...