We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ 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 $\epsilon$, where the communication complexity tends to infinity.

Our main result is the upper bound $C(\epsilon) \leq 1-\Omega\left(\sqrt{H(\epsilon)}\right).$ This compares with Shannon's non-interactive channel capacity of $1-H(\epsilon)$. In particular, for a small enough $\epsilon$, 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(\epsilon) \geq 1-O\left(\sqrt{H(\epsilon)}\right),$ proved for the case where the players take alternating turns.

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ 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 $\epsilon$, where the communication complexity tends to infinity.

Our main result is the upper bound $C(\epsilon) \leq 1-\Omega\left(\sqrt{H(\epsilon)}\right).$ This compares with Shannon's non-interactive channel capacity of $1-H(\epsilon)$. In particular, for a small enough $\epsilon$, 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(\epsilon) \geq 1-O\left(\sqrt{H(\epsilon)}\right),$ proved for the case where the players take alternating turns.