# «Abstract We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 − ǫ) ...»

Towards Coding for Maximum Errors in Interactive Communication

Mark Braverman∗ Anup Rao†

Abstract

We show that it is possible to encode any communication protocol between two parties so that the protocol

succeeds even if a (1/4 − ǫ) fraction of all symbols transmitted by the parties are corrupted adversarially,

at a cost of increasing the communication in the protocol by a constant factor (the constant depends on

epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a 1/8 − ǫ fraction of errors.

1 Introduction Suppose a sender wants to send an n bit message to a receiver, but some of the sender’s transmissions may be received incorrectly. What is the best way to encode the message in order to recover from the errors? This question, ﬁrst considered by Shannon [Sha48], initiated the study of error correcting codes, which have since found applications in many diﬀerent contexts. The book [PWJ72] is a good reference. In our work, we study the analogous question in the more general setting of interactive communication. We refer the reader to the book [KN97] for an introduction to interactive communication protocols. Most models of computation, for example circuits, branching programs, streaming algorithms, distributed systems, inherently involve communication protocols, so the following question is well motivated — What is the best way to encode an arbitrary two party communication protocol, so that the protocol cannot be disrupted by errors in the communication? This more general problem was ﬁrst considered by Schulman [Sch96].

There are several ways to model how errors may occur. Throughout this paper, we focus on the so called worst-case scenario; we only assume that the fraction of transmissions that are received incorrectly is bounded, and make no assumption about the distribution of errors1. For the case of one way communication considered by Shannon, it is known how to construct error correcting codes that can encode any n-bit message using Oǫ (n) bits, so that even if a (1/4 − ǫ) fraction of the transmitted bits are received incorrectly, the intended message can be recovered. If we allow the transmitted message to use symbols from an alphabet whose size depends on ǫ but remains independent of n, it is known how to encode the message so that it can be recovered even if a (1/2 − ǫ) fraction of all symbols are corrupted. Moreover, both the encoding and decoding can be implemented by eﬃcient algorithms. It is impossible torecover from an error rate of 1/2 if one wants to recover the intended message exactly, since there can be no valid decoding of a received string that is equal to each of two valid messages half the time.

In a general interactive protocol, each party must wait for a response from the other party before deciding on what to send in each round of communication, so it is not clear how to use error correcting codes to encode the communication of the protocol. If there are R rounds of communication, any encoding of the protocol that works by encoding each round of communication separately can be disrupted with an error rate of 1/2R — the errors can completely corrupt the shortest message in the protocol. Thus, this approach is not useful if R is ∗ University of Toronto. Email: mbraverm@cs.toronto.edu.

† University of Washington, anuprao@cs.washington.edu. Supported by the National Science Foundation under agreement CCF-1016565.

We do assume that transmissions are received in the order they are sent, and that no transmission is dropped.

large. Nevertheless, Schulman showed that any protocol with T bits of communication can be encoded to give a protocol that uses a constant sized alphabet, communicates at most O(T ) symbols, and tolerates an error rate of 1/240.

1.1 Our Results The main result of our work is a new way to encode protocols to tolerate a large fraction of errors. Given a two party communication protocol π, taking inputs from some ﬁnite set, we write π(x, y) to denote the transcript, namely the sequence of messages exchanged, when π is run with inputs x, y. We shall consider communication protocols that are allowed to send symbols from large alphabets. We write |π| for the maximum number of symbols that can be exchanged on any setting of inputs, namely the communication complexity of π. Of course every communication protocol with a larger alphabet can be simulated by a protocol with a binary alphabet, but this translation can change the error rate that a protocol is resilient to.

**Our ﬁrst result uses a non-binary alphabet:**

** Theorem 1. For every ǫ, there is an alphabet Σ of size Oǫ (1) and a transformation of communication protocols Cǫ, such that for every binary protocol π, Cǫ (π) is a protocol using symbols from Σ, |Cǫ (π)| = Oǫ (|π|), and for all inputs x, y, both parties can determine π(x, y) by running Cǫ (π) if the fraction of errors is at most 1/4 − ǫ.**

In Section 6, we discuss an impossibility result for decoding from larger error rates. We consider the problem where two parties are given bits x, y as inputs and want to compute the parity of the bits. We show that any protocol for this problem that ensures that at each step the parties have a consensus about whose turn it is to transmit (despite arbitrary errors) can be disrupted with an error rate of 1/4. There remains the possibility that the protocol only guarantees a consensus when the error rate is small (say 1/2 − ǫ). For this case, to the best of our knowledge it is possible that some encoding can tolerate an error rate as high as 1/2 − ǫ.

One can encode/decode every alphabet symbol in the protocol of Theorem 1 using an appropriate binary error correcting code to get a protocol that uses the binary alphabet. The resulting protocol would be able to recover from an error rate of (1/16 − ǫ). Our second theorem shows how to do better. We can encode the initial protocol into a protocol using a binary alphabet and tolerate 1/8 − ǫ errors.

** Theorem 2. For every ǫ, there is a transformation of communication protocols Cǫ, such that for every binary protocol π, Cǫ (π) is a binary protocol, |Cǫ (π)| = Oǫ (|π|), and for all inputs x, y, both parties can determine π(x, y) by running Cǫ (π) if the fraction of errors is at most 1/8 − ǫ.**

The bottleneck for proving that our encoding scheme is computationally eﬃcient is the eﬃciency of encoding and decoding tree codes (deﬁned in Section 3). Indeed, if there are polynomial time algorithms for those tasks, then given an algorithm or circuit implementing π, one can very eﬃciently compute an algorithm or circuit implementing Cǫ (π).

The rest of the document is organized as follows. In Section 2 we introduce communication protocols and the pointer jumping problem. In Section 3 we introduce tree codes. In Sections 4 and 5 we discuss how to encode arbitrary communication protocols to tolerate errors using a constant sized alphabet, proving Theorem

1. In Section 7 we discuss how to get a result for binary alphabet proving Theorem 2. In Section 6 we describe the argument to show how one cannot tolerate a 1/4 error rate if the parties are always guaranteed to have consensus about whose turn it is to speak.

2 Communication protocols, pointer jumping and errors Given inputs x, y from some domain, a deterministic protocol with alphabet Σ is a rooted tree where every internal vertex has |Σ| children, each corresponding to an element of the alphabet. Every non-leaf vertex in the tree v is associated with a function fv (x) (or fv (y)) that maps one of the inputs to an element of Σ. The outcome of the protocol on inputs x, y is the unique leaf that is reached by ﬁrst evaluating the function associated with the root, then evaluating the function associated with the child obtained by the ﬁrst evaluation, and so on. The depth of the tree, T is called the communication complexity of the protocol. Two parties who each have access to just one of the inputs can compute the outcome of the protocol by communicating at most T symbols to each other, in the obvious way.

In this paper, we only consider deterministic communication protocols, since our results easily extend to the case of randomized protocols by viewing a randomized protocol as a distribution over deterministic protocols.

Let T be a rooted binary tree of depth T. Let X denote the set of edges leaving vertices at even depth, and Y denote the set of edges leaving vertices at odd depth. Given any set A of edges in the tree, we say that A is consistent if A contains at most one edge leaving every vertex of the tree. We write v(A) to denote the unique vertex of maximal depth that is reachable from the root using the edges of A.

Let X ⊂ X, Y ⊂ Y be consistent subsets. Then observe that X ∪ Y is also consistent. In the pointer jumping problem, the two parties are given such sets X, Y and the goal is compute v(X ∪ Y ). Since every communication protocol with communication complexity t bits can be reduced to solving pointer jumping on a tree of depth 2t, it will suﬃce for us to ﬁnd a protocol that can compute v(X ∪ Y ) even if there are transmission errors.

In this paper, we deﬁne communication protocols that are resilient to transmission errors. In our protocols, every vertex at odd depth will be labeled by a function of the ﬁrst party’s input, and every vertex at even depth will be labeled by a function of the second party’s input2. Given such a protocol, each party runs it as above, using her transmissions and the messages she receives to determine her current position in the protocol tree. In general, each party will conclude the protocol at a diﬀerent leaf.

3 Tree Codes Given a set A, let Ak represent the k-fold Cartesian product A × A ×... × A, and A≤n denote the set ∪n Ak. k=1 A d-ary tree code of depth n and alphabet Σ is a rooted d-ary tree of depth n whose edges are labeled with elements of Σ. The tree deﬁnes an encoding function C : [d]≤n → Σ mapping each vertex in the tree to the label of the ﬁnal edge on the path leading to the vertex. Deﬁne C(v1, v2,..., vk ) to be the concatenation C(v1 ), C(v1, v2 ),..., C(v1,..., vk ). This is just the labels along the path from the root to the vertex v = v1,..., vk.

Given distinct vertices u, v ∈ [d]k at depth k in the tree, we write ℓ(u, v) to denote the quantity k + 1 − minj {uj = vj }, namely the distance to the closest common ancestor in the tree. The tree code has distance α if for any k ∈ {1,..., n} and any distinct u, v ∈ [d]k, C(u1, u2,..., uk ) and C(v1, v2,..., vk ) diﬀer in at least α · ℓ(u, v) coordinates.

**The following theorem was proved in [Sch96]:**

** Theorem 3. For every 0 α 1 there exists a d-ary tree code of depth n and distance α, using an alphabet of size dOα (1).**

Given an arbitrary string z ∈ Σk, we denote by D(z) the vertex v ∈ [d]k that minimizes the hamming distance between C(v1,..., vk ) and z.

4 Recovering from errors using a polynomial size alphabet As a warmup for our construction, we start by showing how to solve the pointer jumping problem even if (1/4 − ǫ) fraction of the transmissions are corrupted, using an alphabet of size polynomial in the depth of T.

Set R = ⌈T /ǫ⌉. Our protocol will be deﬁned over the alphabet Π = {0, 1,..., R} × {0, 1}≤2, We discuss more general types of error correcting protocols, where the turns need not be alternating, in Section 6.

encoded using a tree code. Set d = |Π| and let C : Π≤R → Σ≤R and D : Σ≤R → Π≤R be the encoding and decoding functions of a d-ary tree code of distance 1 − ǫ.

Given any a ∈ Πk, a represents a set of at most k edges in the binary tree T, computed as follows. Let ai = (ri, si ), where ri ∈ {0, 1,..., R} and si ∈ {0, 1}≤2. We think of ri as a pointer to the ri ’th edge determined by a1,..., ari, and of si as specifying an edge that is a descendant of the ri ’th edge.

**Formally, for i = 1,..., k, we use the following procedure to determine an edge ei from a:**