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).
Over the last years, there has been great interest in interactive protocols, considering various properties of such protocols such as their efficiency @cite_13 @cite_7 (stochastic noise), @cite_4 @cite_20 @cite_24 @cite_33 (adversarial noise), their noise resilience under different assumptions and models @cite_15 @cite_18 @cite_30 @cite_6 , their information rate @cite_1 @cite_27 @cite_25 @cite_12 and other properties, such as privacy @cite_5 @cite_31 or list-decoding @cite_22 @cite_24 @cite_32 . We stress that all the works prior to this work (and to the independent work @cite_22 @cite_24 ), assume the robust, non-adaptive setting.
@cite_30 @cite_18 @cite_31 @cite_4 @cite_33 @cite_7 @cite_22 @cite_1 @cite_32 @cite_6 @cite_24 @cite_27 @cite_5 @cite_12 @cite_15 @cite_13 @cite_25 @cite_20
1963163055 2072979474 2481902600 2296697369
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). In this work, we study the problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given an interactive protocol which is designed to run on an error-free channel, construct a protocol that evaluates the same function (or, more generally, simulates the execution of the original protocol) over a noisy channel. As in (non-interactive) error correcting codes, the noise can be either stochastic, i.e. drawn from some distribution, or adversarial, i.e. arbitrary subject only to a global bound on the number of errors. We show how to simulate any interactive protocol in the presence of constant-rate noise, while incurring only a constant blow-up in the communication complexity (CC). Our simulator is randomized, and succeeds in simulating the original protocol with probability at least @math . 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 nonadaptive protocol can withstand is 1 3. In addition, we provide a simple and efficient nonadaptive coding scheme that succeeds as long as the fraction of noise is at most @math . 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 coding scheme that withstands the optimal tolerable erasure rate of @math [ , IEEE Trans. Info. Theory , 2015], but operates in a much simpler and more efficient way than the previous schemes. Our coding scheme works with an alphabet of size 4, in contrast to prior schemes in which the alphabet size grows as @math . 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 @math . We study efficient, deterministic interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length. For channels that flip bits independently with probability e For channels in which an adversary controls the noise pattern our coding scheme can tolerate Ω(1 log n) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encodable and decodable systematic tree code of length n that has relative distance Ω(1 log n) and rate approaching 1, defined over an O(log n)-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate 1 - O([EQUATION]) in the random error model, and approaching rate 1 in the adversarial error model.