EE Seminar: Interactive Coding Over the Noisy Broadcast Channel
(The talk will be given in English)
Speaker: Dr. Klim Efremenko
Cs, Ben Gurion University
Monday, April 16th, 2018
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Interactive Coding Over the Noisy Broadcast Channel
Abstract
In this talk, we show first constant rate coding scheme for a noisy broadcast model
defined by El Gamal in 1984. In this model, a set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed?
The best know protocol before our work was given in 1988 by Gallager, who gave an elegant noise-resistant protocol requiring with 1/log log n rate. We show that constant rate is possible. We will do so by exploiting the power of adaptive protocols.
