| When two remote parties wish to perform some computation given that their communication channel may be noisy, sophisticated coding schemes must be employed in order to resist a constant fraction of noise while increasing the communication by only a constant factor. The ultimate goal is to find computationally efficient schemes that resist the maximal possible amount of noise while transmitting as few bits as possible.;In this work we examine two properties of such interactive schemes: their computational efficiency and their noise resilience. First, we show how to obtain an efficient scheme that is resilient to random errors (where each bit is flipped with constant probability). Next, we consider the case of adversarial noise (where we only limit the total amount of flipped bits) and obtain a scheme that is resilient to noise rates up to 1/2, given simple setup assumptions. All our schemes feature constant communication overhead.;Similar techniques can also be applied to the problem of communicating a data stream over a noisy channel, for which we achieve an optimal and efficient scheme that resists noise rates less than one. |
