A Lower Bound for Cooperative Broadcast in the presence of Noise

In a noisy broadcast channel, processors communicate as follows: in each time step, a pre-designated processor broadcasts a bit. Each of the other processors receives a bit, but the received bit is incorrect with some given probability p. Reception errors are assumed to be independent.

In such an environment, a group of n broadcasters, each possessing a bit, wish to transmit all n bits to a receiver so that, with probability close to 1, the receiver learns all of the bits correctly. This can be done easily with O(n log n) broadcasts, by having each processor broadcast its input bit C log n times (for some sufficiently large constant C) and having the receiver decode each bit by majority vote. Gallagher, in 1988, gave a protocol using only O(n log log n) broadcasts.

I’ll describe a recent result, obtained with Navin Goyal and Guy Kindler, showing that Gallagher’s protocol is optimal up to a constant factor.