Computer Science/Discrete Mathematics Seminar II | |

Topic: | Interactive Channel Capacity |

Speaker: | Gillat Kol |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, November 19 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2013/1119-GillatKol |

In a profoundly influential 1948 paper, Claude Shannon defined the entropy function \(H\), and showed that the capacity of a symmetric binary channel with noise rate (bit flip rate) \(\mathrm{eps}\) is \(1-H(\mathrm{eps})\). This means that one can reliably communicate \(n\) bits by sending roughly \(n / (1-H(\mathrm{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 a noisy channel when it is used interactively. We define interactive channel capacity as the minimal ratio between the communication required to compute a function (over a non-noisy channel), and the communication required to compute the same function over the \(\mathrm{eps}\)-noisy channel. We show that the interactive channel capacity is roughly \(1-\Theta\left( \sqrt{H(\mathrm{eps})} \right)\). Our result gives the first separation between interactive and non-interactive channel capacity. Joint work with Ran Raz.