Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring @math bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires @math knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips @math bits, our algorithm sends @math bits in expectation and succeeds with high probability in @math . It does so without any @math knowledge of @math . Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.
Schulman's scheme tolerates an adversarial noise rate of @math . It critically depends on the notion of a tree code for which an exponential-time construction was originally provided. This exponential construction time motivated work on more efficient constructions @cite_14 @cite_4 @cite_8 . There were also efforts to create alternative codes @cite_26 @cite_24 . Recently, elegant computationally-efficient schemes that tolerate a constant adversarial noise rate have been demonstrated @cite_27 @cite_17 . Additionally, a large number of powerful results have improved the tolerable adversarial noise rate @cite_15 @cite_10 @cite_19 @cite_13 @cite_0 .
@cite_13 @cite_14 @cite_4 @cite_26 @cite_8 @cite_24 @cite_19 @cite_27 @cite_0 @cite_15 @cite_10 @cite_17
2296697369 2481902600 2026670837 2145385126
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 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 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. Consider two parties who wish to communicate in order to execute some interactive protocol π. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of π (which was designed for an error-free channel). If π only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol π, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of π (which we denote by N). In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(N), has failure probability roughly 2-N, and is resilient to 1 32-fraction of adversarial error. The second runs in time O(N log N), has failure probability roughly 2-N, and is resilient to some constant fraction of adversarial error. The third runs in time O(N), has failure probability 1 poly(N), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made deterministic if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance).