CODING FOR INTERACTIVE COMMUNICATION

Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol pi be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction, We study the following questi on: If in fact the channel is noisy, what is the effect upon the numbe r of transmissions needed in order to solve the computation problem re liably? Technologically this concern is motivated by the increasing im portance of communication as a resource in computing, and by the trade off in communications equipment between bandwidth, reliability, and ex pense. We treat a model with random channel noise. We describe a deter ministic method for simulating noiseless-channel protocols on noisy ch annels, with only a constant slowdown. This is an analog for general i nteractive protocols of Shannon's coding theorem, which deals only wit h data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are det ermined only one at a time, dynamically, in the course of the interact ion, Instead, we describe a simulation protocol using a new kind of co de, explicit tree codes.