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.