A Lower Bound for Cooperative Broadcast in the presence of Noise

  • Michael Saks | Rutgers University

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.

发言人详细信息

Michael Saks is a professor in the mathematics department at Rutgers University, working in theory of computing and discrete mathematics.

接下来观看