Initiated by Schulman, the focus of interactive coding has been the ability to communicate at constant overhead (compared to the noiseless case) under a constant rate of adversarial noise (see, e.g., choice nr. 90). Whenever the rate of noise was considered, the focus was on trying to have it as large as possible. In contrast, the current paper asks about the exact level of the communication overhead as a function of the (random) noise rate, and its focus is on a low level of noise (and the noise is random rather than adversarial). For sufficiently low rate of random noise, the said interactive overhead (i.e., the reciprocal of the channel capacity) is shown to be larger than in the (classical) non-interactive case.
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
See ECCC TR13-001