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.
The seminal work of Schulman @cite_3 @cite_12 overcame these obstacles by describing a deterministic method for simulating interactive protocols on noisy channels with only a constant-factor increase in the total communication complexity. This work spurred vigorous interest in the area (see @cite_16 for an excellent survey).
@cite_16 @cite_12 @cite_3
2072979474 2145385126 2026670837 2407991844
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 . 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). 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 as he pleases, thus interrupting the execution of π (which was designed for an errorless channel). If π only contained one message, then a good error correcting code would have overcame the noise with only a constant overhead in communication, but this solution is not applicable to interactive protocols with many short messages. Schulman (FOCS 92, STOC 93) presented the notion of interactive coding: A simulator that, given any protocol π, is able to simulate it (i.e. produce its intended transcript) even with constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. Until recently, however, the running time of all known simulators was exponential (or sub-exponential) in the communication complexity of π (denoted N in this work). Brakerski and Kalai (FOCS 12) recently presented a simulator that runs in time poly (N). Their simulator is randomized (each party flips private coins) and has failure probability roughly 2−N. In this work, we improve the computational complexity of interactive coding. While at least N computational steps are required (even just to output the transcript of π), the BK simulator runs in time