TIME: 1:30-2:20 pm,  April 11, 2006

PLACE: CSE 403

TITLE: Gallager's cooperative broadcast problem: new lower-bounds for noisy 
communication

SPEAKER:  Guy Kindler
          Microsoft Research

ABSTRACT:
The effect of noise on computation and communication has been studied
extensively in recent decades.  This field of research can be traced back
to Shannon, who proved that transferring information from one party to
another over a noisy channel requires only a constant blowup in resource
usage, compared to transmission over a noise free channel. Over the years
it was shown that a constant blowup is sufficient to overcome noise in
many other models.

In this talk I will discuss a model introduced by El Gamal in 1984 for
sharing information over a noisy broadcast network: each of N players
is given one input bit, and the goal is for all players to learn (with
high probability) all the input bits of the other players, using the
smallest possible number of broadcasts over a joint communication
channel. In each broadcast a player transmits one bit to all other
players; however noise flips the bit heard by each recipient with some
fixed probability.

In a noise-free channel, N broadcasts would trivially suffice for all
players to learn all bits. However the best known protocol for noisy
channels, discovered by Gallager in 1988, uses Nloglog(N) broadcasts.
Determining whether a linear number of broadcasts can be achieved has
remained a well known open problem since Gallager's work. We resolve
this problem, showing that every protocol for this task requires at
least cNloglog N broadcasts for some absolute constant c.

This is joint work with Navin Goyal and Michael Saks.