Key points are not available for this paper at this time.
Shannons Coding Theorem shows that in order to reliably transmit a message of T bits over a noisy communication channel, only a constant slowdown factor is necessary in the case when the channel is noisy, relative to the case in which the channel is noiseless. (The time required is asymptotically C , where 0 ! C 1 is the Shannon capacity, a function only of the noise characteristics.) The theorem ensures that the probability of a decoding error is exponentially small in the message length T . Recently the second author obtained an analogous result for arbitrary interactive communication protocols between two processors. In the present
Rajagopalan et al. (Sat,) studied this question.