We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any robust protocol can resist is 1 3. Additionally, we provide a simple and efficient robust protocol that succeeds as long as the fraction of noise is at most 1 3 - . Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a protocol that matches the optimal tolerable erasure rate of 1 2 - of previous protocols (, CRYPTO '13) but operates in a much simpler and more efficient way. Our protocol works with an alphabet of size 4, in contrast to prior protocols in which the alphabet size grows as epsilon goes to zero. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1 3 - .
Protocols in the above works are all robust. The discussion about non-robust or protocols was initiated by Ghaffari, Haeupler and Sudan @cite_15 @cite_16 and concurrently by Agrawal, Gelles and Sahai @cite_6 , giving various notions of adaptive protocols and analyzing their noise resilience. Both the adaptive notion of @cite_15 @cite_16 and of @cite_6 are capable of resisting a higher amount of noise than the maximal @math allowed for robust protocols. Specifically, a tight bound of @math was shown in @cite_15 @cite_16 for protocols of fixed length; when the length of the protocol may adaptively change as well, a coding scheme that achieves a noise rate of @math is given in @cite_6 , yet that scheme does not have a .
@cite_15 @cite_16 @cite_6
2040355376 1963163055
We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings. Most significantly, we explore adaptive interactive communication where the communicating parties decide who should speak next based on the history of the interaction. In particular, this decision can depend on estimates of the amount of errors that have occurred so far. Braverman and Rao [STOC'11] show that non-adaptively one can code for any constant error rate below 1 4 but not more. They asked whether this bound could be improved using adaptivity. We answer this open question in the affirmative (with a slightly different collection of resources): Our adaptive coding scheme tolerates any error rate below 2 7 and we show that tolerating a higher error rate is impossible. We also show that in the setting of [CRYPTO'13], where parties share randomness not known to the adversary, adaptivity increases the tolerable error rate from 1 2 to 2 3. For list-decodable interactive communications, where each party outputs a constant size list of possible outcomes, the tight tolerable error rate is 1 2. Our negative results hold even if the communication and computation are unbounded, whereas for our positive results communication and computations are polynomially bounded. Most prior work considered coding schemes with linear communication bounds, while allowing unbounded computations. We argue that studying tolerable error rates in this relaxed context helps to identify a setting's intrinsic optimal error rate. We set forward a strong working hypothesis which stipulates that for any setting the maximum tolerable error rate is independent of many computational and communication complexity measures. We believe this hypothesis to be a powerful guideline for the design of simple, natural, and efficient coding schemes and for understanding the (im)possibilities of coding for interactive communications. How much adversarial noise can protocols for interactive communication tolerate? This question was examined by Braverman and Rao (IEEE Trans. Inf. Theory, 2014) for the case of "robust" protocols, where each party sends messages only in fixed and predetermined rounds. We consider a new class of non-robust protocols for Interactive Communication, which we call adaptive protocols. Such protocols adapt structurally to the noise induced by the channel in the sense that both the order of speaking, and the length of the protocol may vary depending on observed noise. We define models that capture adaptive protocols and study upper and lower bounds on the permissible noise rate in these models. When the length of the protocol may adaptively change according to the noise, we demonstrate a protocol that tolerates noise rates up to @math . When the order of speaking may adaptively change as well, we demonstrate a protocol that tolerates noise rates up to @math . Hence, adaptivity circumvents an impossibility result of @math on the fraction of tolerable noise (Braverman and Rao, 2014).