Alice and Bob want to run a protocol over an unreliable channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring L 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 a priori knowledge of the number of bits that will be flipped by the adversary. Here, we describe an algorithm requiring no such knowledge. If an adversary flips T bits, our algorithm sends L + O (T + √ LT + L) log(LT + L) bits in expectation and succeeds with high probability in L. It does so without any a priori knowledge of T . 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 such an assumption is necessary when the amount of noise is unknown. Our Results. Our main result is summarized in the following theorem. Theorem 1. Algorithm 15 (Section 2) tolerates an unknown number of adversarial errors, T , succeeds with high probability in the transcript length 3 , L, and if successful, sends L + O (T + √ LT + L) log(LT + L) bits in expectation. We show in Theorem 5 (Section B) that the number of bits sent by our algorithm is within logarithmic factors of optimal, assuming a conjecture from [12] . As additional results, we demonstrate a relationship between the overhead incurred when T = 0 and when T ≥ 1 for a very general class of algorithms, and derive some near-optimal results under this class (Section B). Challenges. Can we adopt prior results by guessing the noise rate in advance? An underestimate threatens correctness if the actual number of bit flips exceeds what the algorithm can tolerate. Conversely, an overestimate leads to sending more bits than necessary. Thus, we need a protocol that adapts to the adversary's actions. One idea is to adapt the amount of communication redundancy based on the number of errors detected thus far. However, this presents a new challenge because the parties may have different views of the number of errors. They will need to synchronize their adaptions over the noisy channel. Another technical challenge is termination, because the length of the simulated protocol is necessarily unknown. This means that the parties will likely not terminate at the same time. After one party has terminated, it is a challenge for the other party to detect this fact based on bits received over the noisy channel. For L bits to be transmitted from Alice to Bob, Shannon [20] proposes an error correcting code of size O(L) that yields correct communication over a noisy channel with probability 1 − e −Ω(L) . At first glance, this may appear to solve our problem. But consider an interactive protocol with communication complexity L, where Alice sends one bit, then Bob sends back one bit, and so forth where the value of each bit sent depends on the previous bits received. Two problems arise. First, using block codewords is not efficient; to achieve a small error probability, "dummy" bits may be added to each bit prior to encoding, but this results in a superlinear blowup in overhead. Second, due to the interactivity, an error that occurs in the past can ruin all computation that comes after it. Thus, error correcting codes fall short when dealing with interactive protocols. The seminal work of Schulman [18, 19] overcome 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 has spurred a vigorous interest in the area (see [4] for an excellent survey). Schulman's scheme tolerates an adversarial noise rate of 1/240, and it is critically dependent on the notion of a tree code for which an exponential-time construction was originally provided. This latter property has motivated work on more efficient constructions [5, 13, 17] , and other attempts have focused on useful alternative codes [9, 16] . Elegant computationally-efficient schemes that can tolerate a constant adversarial noise rate have been demonstrated [1, 10] . Additionally, a large number of powerful results have improved the tolerable adversarial noise rate [2, 3, [6] [7] [8] 11 ]. 3 Specifically with probability at least 1 −
We note that the problem in this paper can be viewed as a special case of interactive communication in the model from REF , where the protocol π just sends L bits from Alice to Bob.
Interactive Communication with Unknown Noise Rate
ArXiv
ArXiv
Computer Science Mathematics