A coding theorem for distributed computation

Shannon's 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