EE Seminar: Dr. Gillat Kol

~~(The talk will be given in English)

Speaker: Dr. Gillat Kol
Institute for Advanced Study (IAS), Princeton
Wednesday, January 14th, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

Interactive Channel Capacity

Abstract
In a profoundly influential 1948 paper, Claude Shannon defined the entropy function H, and showed that the capacity of the eps-BSC, the binary symmetric channel with crossover probability eps, is 1-H(eps). This means that one can reliably communicate n bits by sending roughly n / (1-H(eps)) bits over this channel.
The extensive study of interactive communication protocols in the last decades gives rise to the related question of finding the capacity of the eps-BSC when it is used interactively. We define interactive channel capacity as the minimal ratio between the communication required to compute a function (over a noiseless channel), and the communication required to compute the same function over the eps-BSC. We show that the interactive channel capacity is roughly 1 - c * sqrt(H(eps)), for some constant c. Our result gives the first separation between interactive and non-interactive channel capacity.
Joint work with Ran Raz.