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.
展开▼
