## Interactive Channel Capacity

by Gillat Kol and Ran Raz.

We study the interactive channel capacity of an $\eps$-noisy channel. The interactive channel capacity $C(\eps)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel) and the communication complexity of the same problem over the binary symmetric channel with noise rate $\eps$, where the communication complexity tends to infinity.
Our main result is the upper bound $C(\eps) \leq 1-\sqrt{H(\eps)}$. This compares with Shannon's non-interactive channel capacity of $1-H(\eps)$. In particular, for a small enough $\eps>0$, our result gives the first separation between interactive and non-interactive channel capacity, answering an open problem by Schulman
We complement this result by the lower bound $C(\eps) \geq 1-\sqrt{H(\eps)}$ proved for the case where the players take alternating turns