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

Our main result is the upper bound C()1−H() This compares with Shannon's non-interactive channel capacity of 1−H(). In particular, for a small enough , 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()1−OH() proved for the case where the players take alternating turns.