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 - .
As mentioned above, the question of interactive communication over a noisy channel was initiated by Schulman @cite_0 @cite_5 @cite_7 who mainly focused on the case of random bit flips, but also showed that his scheme resists an adversarial noise rate of up to @math . Braverman and Rao @cite_19 proved that @math is a tight bound on the noise (for large alphabets), and Braverman and Efremenko @cite_20 gave a refinement of this bound, looking at the noise rate separately at each direction of the channel (i.e., from Alice to Bob and from Bob to Alice). For each pair of noise rates, they determine whether or not a coding scheme with a exists. Another line of work improved the efficiency of coding schemes for the interactive setting, either for random noise @cite_9 @cite_4 , or for adversarial noise @cite_3 @cite_12 @cite_16 .
@cite_4 @cite_7 @cite_9 @cite_3 @cite_0 @cite_19 @cite_5 @cite_16 @cite_12 @cite_20
2481902600 2296697369 2026591308 2026670837
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. We provide the first capacity approaching coding schemes that robustly simulate any interactive protocol over an adversarial channel that corrupts any @math fraction of the transmitted symbols. Our coding schemes achieve a communication rate of @math over any adversarial channel. This can be improved to @math for random, oblivious, and computationally bounded channels, or if parties have shared randomness unknown to the channel. Surprisingly, these rates exceed the @math interactive channel capacity bound which [Kol and Raz; STOC'13] recently proved for random errors. We conjecture @math and @math to be the optimal rates for their respective settings and therefore to capture the interactive channel capacity for random and adversarial errors. In addition to being very communication efficient, our randomized coding schemes have multiple other advantages. They are computationally efficient, extremely natural, and significantly simpler than prior (non-capacity approaching) schemes. In particular, our protocols do not employ any coding but allow the original protocol to be performed as-is, interspersed only by short exchanges of hash values. When hash values do not match, the parties backtrack. Our approach is, as we feel, by far the simplest and most natural explanation for why and how robust interactive communication in a noisy environment is possible. We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memory less noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman [Schulman 1993] our simulation uses a tree-code, yet as opposed to the non-constructive absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an explicit emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.