Coding for interactive communication correcting
insertions and deletions

arXiv:1508.00514v2 [cs.DS] 24 May 2016

Mark Braverman∗

Ran Gelles†

Jieming Mao‡

Rafail Ostrovsky§

May 25, 2016

Abstract
We consider the question of interactive communication, in which two remote parties perform
a computation while their communication channel is (adversarially) noisy. We extend here the
discussion into a more general and stronger class of noise, namely, we allow the channel to
perform insertions and deletions of symbols. These types of errors may bring the parties “out
of sync”, so that there is no consensus regarding the current round of the protocol.
In this more general noise model, we obtain the first interactive coding scheme that has a
constant rate and tolerates noise rates of up to 1/18−ε. To this end we develop a novel primitive
we name edit distance tree code. The edit distance tree code is designed to replace the Hamming
distance constraints in Schulman’s tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem
to yield a primitive that suffices for communication in the presence of synchronization problems.
Giving the “right” definition of edit distance tree codes is a main conceptual contribution of
this work.

1

Introduction

In the setting of interactive communication two remote parties, Alice and Bob, wish to run a distributed protocol utilizing a noisy communication channel. The study of this problem was initiated
by the seminal work of Schulman [25, 27, 28] who showed a coding scheme for interactive protocols
in which the communication complexity of the resilient protocol is larger than the communication
of the input (noiseless) protocol by only a constant factor. Schulman’s coding schemes tolerates
random noise where each bit is flipped with a small probability, as well as some adversarial noise
∗

Department of Computer Science, Princeton University, email: mbraverm@cs.princeton.edu. Research supported
in part by an an NSF CAREER award (CCF-1149888), NSF CCF-1215990, a Turing Centenary Fellowship, a Packard
Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
†
Department of Computer Science, Princeton University, email: rgelles@cs.princeton.edu
‡
Department of Computer Science, Princeton University, email: jiemingm@cs.princeton.edu
§
Department of Computer Science and department of Mathematics, UCLA, email: rafail@cs.ucla.edu. Work supported in part by NSF grants 09165174, 1065276, 1118126 and 1136174, DARPA, US-Israel BSF grant 2008411,
OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. The views
expressed are those of the author and do not reflect the official policy or position of the Department of Defense or
the U.S. Government.

1

where the only restriction on the noise is the amount of bits being flipped by the adversary. Subsequently, many works considered the question of interactive communication, obtaining coding
schemes reaching optimality in terms of their computational efficiency [14, 15, 3, 5, 4, 16], communication efficiency [20, 18, 13], and noise resilience, both in the standard setting [9, 7, 8, 16], and
in various other noise models and settings [24, 23, 11, 12, 17, 16, 1, 6, 10].
The recent successes in developing the theory of interactive error-correcting codes brought the
study of two-way interactive coding to nearly match what we know about good codes against
adversarial noise in the one-way setting.
So far, all works focused on either substitutions (where Eve can substitute a sent symbol with a
different symbol from the alphabet) or erasures (where Eve can substitute a sent symbol with a ⊥).
In this work we extend the question of coding for interactive communication over noisy channels to
a more general type of noise. Namely, we consider channels with insertions and deletions (indels).
In the one-way setting, this corresponds to the insertion and deletion model, where Eve is allowed
to completely remove transmitted symbols, or inject new symbols. Note that this model is stronger
than the substitution model, since a substitution can always be implemented as a deletion followed
by an insertion. Even in the one-way regime, this model is more difficult to analyze than the model
with substitution errors. As an example, Schulman and Zuckerman [26] gave a polynomial-time
1
encodable and decodable codes for insertion/deletion errors. Their code can tolerate around 100
fraction of insertion/deletion errors. This should be contrasted with efficient codes in the standard
noise setting, e.g., [19], tolerating about 41 fraction of bit flips.
The major additional challenge in dealing with indels in the interactive setting compared to
the non-interactive indel model and the interactive substitutions model, is that we can no longer
assume that Alice and Bob are synchronized: at a given time they may be at different stages of
their sides of the protocol! Indeed, if Eve deletes Alice’s transmission to Bob and additionally
injects a ‘spoofed’ reply from Bob back to Alice, then while Bob has received no message and
assumes the protocol hasn’t advanced yet, Alice has received a spoofed reply, and proceeds to the
next step of her protocol. From this point and on, unless the insertion/deletion is detected, the
parties are unsynchronized, as they run different steps of the protocol. The challenge in dealing
with this model is to design a protocol that manages to succeed even without knowing whether the
two parties are synchronized.

1.1

Modeling insertions and deletions

Some care is required when dealing with insertion and deletion noise patterns, as certain choices
make the model too strong or too weak. For example, consider the case where Alice and Bob send
each other symbols in an alternating way. Then, even if a single deletion of a symbol is allowed the
noise can cause the protocol to “hang”: Bob will be waiting for a symbol from Alice, while Alice
will be waiting for Bob’s response. Clearly, such a model is too strong for our purpose, and we
should restrict the allowed noise patterns to preserve the protocol’s liveliness.
There are two main paradigms for distributed protocol in which parties are not fully-synchronized.
The first is a message-driven paradigm, in which each party “sleeps” until the arrival of a new message that triggers it into performing some computation and sending a message to the other party.
The second is clock-driven, where each party holds a clock: each clock tick, the party wakes up,
checks the incoming messages queue, performs some computation, and sends a message to the other
side. The issue here is that different parties may have mismatching or skewed clocks. Then, instead

2

of acting in an alternating manner, one party may wake up several times while the other party is
still asleep.
We emphasize that if the parties have matching clocks, then no insertions and deletions are
possible—channel corruption in this case has either the effect of changing one symbol to another
(as in a standard noisy channel), or causing a detectible corruption, i.e., an erasure. Both these
types of noise are substantially weaker than insertions and deletions, and were already analyzed in
previous work (e.g., [28, 7, 12, 10]).
Our noise model, which we describe shortly, makes sense for both the above paradigms: it
guarantees liveliness in a message-driven setting; for the clock-driven model, we can show that any
such settings reduces to our model, that is, any resilient protocol in our model can be used to obtain
a resilient protocol in the clock-driven setting. The skewness of the clocks in that case, is related
to the noise-resilience of the protocol in our model. See the full version for the complete details.
In this work we assume a message-driven setting, where the parties normally speak in alternating
manner. Any corruption in our model must be a deletion which is followed by an insertion. We
name each such tampering as an edit corruption.
Definition 1.1 (Edit Corruption). An edit-corruption is a single deletion followed by a single
insertion (whether the inserted symbol is aimed at the same or the opposite party as the deleted
message).
This gives rise to two types of attacks Eve can perform: (i) delete a symbol and replace it with
a different symbol (insert a symbol at the same direction as the deleted symbol; a substitution
attack); (ii) delete a symbol, and insert a spoofed reply from the other side (insert a symbol at the
opposite direction of the deleted symbol). The second type of corruption has an effect of making
the parties ‘out-of-sync’: one party advances one step in the protocol, while the other does not;
see Figure 1. Note that a substitution has a cost a single corruption, i.e., it is counted as a single
deletion followed by a single insertion. Also note that although an outside viewer can split Eve’s
attack into pairs of deletion-and-insertion, the string that a certain party receives, from that party’s
own view, suffers an arbitrary pattern of insertions/deletions.

Alice
rndA
i

Bob
σ′

σ

i+1

Alice
rndB
i′

rndA
i

i′ + 1

i+1

(i)

Bob
rndB
i′

σ
σ′

i′

(ii)

Figure 1: An illustration of the two insertion/deletion attacks: (i) a deletion followed by an insertion in the
same direction (a substitution); (ii) a deletion followed by an insertion to the opposite direction (an out-ofsync attack). The deleted transmission is marked with a cross, and the inserted transmission is marked with
a bold arrow. The dashed arrow denotes a possible (non-interrupted) reply.

3

1.2

Our Results and Techniques

Tree codes with edit distance. When only a single message is to be transmitted (i.e., in the oneway setting), codes that withstand insertions and deletions were first considered by Levenshtein [22].
In such codes, each two codewords must be far away in their edit distance, a notion of distance that
captures the amount of insertions/deletions it takes to convert one codeword to another. The edit
distance replaces the Hamming distance, which essentially counts the amount of bit flips required
to turn one codeword to another.
A key ingredient in interactive-communication schemes is the tree code [28], a labeled tree such
that the labels on each descending path in the tree can be seen as a codeword. The tree code is
parametrized by a distance parameter α, and it holds that any two codewords whose paths diverge
from the same node, are at least α-apart in their Hamming distance. Encoding a message via a
tree code allows a party to eventually obtain the message sent by the other side, as long as not
too many errors have happened. This in turn allows the parties to correct errors that previously
occurred in the simulation, and revert the simulation back into a correct state [28, 7]. In order to
keep the communication overhead a constant factor when tree code encoding is used in interactive
schemes, it is required that each label of the tree comes from an alphabet of constant size (that is,
the size of the alphabet is independent of the tree’s depth and thus independent of the length of
protocol to simulate).
It is only natural to believe that we could obtain interactive-communication schemes that withstand insertions/deletions by replacing tree codes with a stronger notion of codes, namely, edit
distance tree codes. In edit distance tree codes, each two codewords (possibly of different lengths)
which diverge at a certain point, are required to be far apart in their edit distance rather than their
Hamming distance. Yet, since the parties are not synchronized, new difficulties arise. To give a
simple example, assume Alice sends one of the two following encodings s1 = ABCAAABBB and
s2 = ABCABCAAA, and assume Bob has receives the string ABCBBB. If Bob knew that Alice
thinks she is in round 6 of the protocol, he would decode to s2 ; if he knew that Alice thinks she is
in round 9, he would decode to s1 . Alas, he does not know which is the case!
To mitigate situations in which not being synchronized may hurt us, we require an even stronger
property, namely, we wish that the suffixes (of arbitrary lengths) of any two overlapping codewords
will have appropriately large edit distance (See Definitions 3.2 and 3.3 for the precise condition).
This stronger property guarantees that two “branches” in the tree are far apart in their edit distance,
even when they are shifted with respect to each other due to lack of synchronization possibly caused
by previous indels. We can then show that as long as not too many indels occurred in the suffix of
the received codeword, the tree-code succeeds to recover the entire sent message. Crucial in this
approach is a notion of distance we call suffix distance (Definition 3.9), that measures the amount
of noise in a codewords’ suffix. This generalizes a distance measure by Franklin et al. [11, 12] (see
also Braverman and Efremenko [8]) to the case where the received word may be misaligned with
respect to the sent word, due to indels.
Alas, while (Hamming distance) tree codes over a constant alphabet were shown to exist by
Schulman [28], it is not clear if such trees exist for edit distance, and if so, for which distance
parameter α, as Schulman’s proof doesn’t carry over to the edit distance case. Our first result
(Section 3) shows the existence of edit distance tree codes, for any distance parameter α,
Theorem 1.2 (Informal). For any α < 1 and any d, n ∈ N there exists a d-ary edit distance tree
code of depth n over a constant-size alphabet.

4

In section 3 we prove the existence of such trees and prove the above lemma. Similarly to [28],
the proof is inductive in the depth of the tree, but the inductive statement needs to be further
strengthened in order for the induction to go through.
As in the case of standard tree codes, finding an efficient construction for such trees remains
an important open question. Building on the techniques of Gelles, Moitra and Sahai [14, 15] we
give in Appendix E an efficient randomized construction of a relaxed notion for edit-distance tree
codes, we call a potent edit distance tree codes (see Definition E.2 for the precise definition of potent
edit-distance tree codes). These trees satisfy the edit-distance guarantee almost everywhere, and
are good enough to replace the tree-code notion of Theorem 1.2 in most applications.
Theorem 1.3 (Informal). For any α < 1 and any d, n ∈ N there exists a construction of a d-ary
potent edit distance tree code of length n over a constant-size alphabet. The construction is efficient
and succeeds with overwhelming probability (in n).
While in the rest of the paper (namely, for our coding scheme) we assume the edit-distance
notion of Theorem 1.2, all our schemes work the same when the tree is replaced with a potent one,
see Appendix F for further details.
Interactive-communication schemes tolerating insertions/deletions. Equipped with edit
distance tree codes, we show a protocol that solves the pointer jumping problem over a noisy channel with insertions and deletions and exhibits linear communication complexity in the noiseless
communication. Since the pointer jumping problem is complete for two-party interactive communication, this implies a coding scheme that can simulate any protocol over a channel that may
introduce insertion/deletions. Specifically, in Sections 4 and D we show that for any ε > 0 and any
noiseless protocol π and inputs x, y, there is a scheme that correctly simulates π (that is, produces
the transcript π(x, y) at both parties), withstands 1/18 − ε fraction of edit-corruptions, and has a
linear communication complexity with respect to the communication of the protocol π.
Theorem 1.4. For any ε > 0, and for any binary (noiseless) protocol π with communication
CC(π), there exists a noise-resilient coding scheme with communication Oε (CC(π)) that succeeds
in simulating π as long as the adversarial edit-corruption rate is at most 1/18 − ε.
Our coding scheme and analysis follows ideas by Braverman and Rao [7] and by Braverman and
Efremenko [8]—first focusing on channels with polynomial-size alphabet and then generalizing to
channels with constant-size alphabet—however, the analysis in the light of insertions and deletions
is more complicated and subtle. In particular, similar to [8], our analysis uses the notion of suffix
distance for relating the effect of the noise to the progress of the simulation.
We note again that due to out-of-sync attacks, it is possible that the parties’ belief of the
“current” round of the protocol is different. In the worst case, while Alice reaches the end of the
coding protocol (say, round N ), it is possible that Bob has only reached round (1 − 2ρ)N , e.g.,
due to 2ρN deletions in his received communication (ρ is the fraction of edit-corruptions in that
instance). Therefore, if we wish to tolerate a ρ-fraction of edit-corruptions, it is imperative that the
parties output the correct answer already at round (1 − 2ρ)N . Our coding scheme (Theorem 1.4)
satisfies even this more strict requirement.
Finally, in Appendix G we show that for a family of rigid protocols, in which we require both
parties to output the correct value at round (1 − 2ρ)N , then ρ = 1/6 is an upper bound on the
admissible edit-corruption rate.
5

Theorem 1.5 (Informal). If both parties are required to give output at round (1 − 2ρ)N , then no
coding scheme of length N can tolerate an edit-corruption rate of ρ = 1/6.
Closing the gap between the upper bound of 1/6, and the resilience 1/18 achieved by the scheme
of Theorem 1.4 is left for future work.

2

Preliminaries

For any finite set S, we denote by x←S the case that x is uniformly distributed over S. All
U

logarithms are taken to base 2. We denote the set {1, 2, . . . , n} by [n]. For a set Σ we denote
Σ≤n = ∪0≤i≤n Σi , and Σ∗ = ∪i≥0 Σi . Let s ∈ Σl be a string of length |s| = l. For 1 ≤ i ≤ j ≤ l, we
use s[i] to denote the i-th symbol of s and s[i..j] to denote the string s[i] ◦ s[i + 1] ◦ · · · ◦ s[j].
Definition 2.1 (Pointer Jumping Problem). Any communication protocol of T rounds where the
parties alternately exchange bits can be reduced to the following pointer jumping problem P JP (T ):
Let T be a binary tree of depth T . Alice’s input X is a set of consistent edges leaving vertices at
even depths. Bob’s input Y is a set of consistent edges leaving odd-level vertices. A set of edges is
consistent on a specified set of vertices, if it contains exactly one edge leaving every vertex in that
specified set. Due to being consistent on all the nodes, X ∪ Y defines a unique root-to-leaf path.
The parties’ goal is to output this unique path. Note that T alternating rounds of communication
suffice to compute this path, assuming noiseless channels.
Definition 2.2 (Protocols). An interactive protocol π for a function f (x, y) is a distributed algorithm that dictates for each party, at every round, the next message (symbol) to send given the
party’s input and the messages received so far. Each transmitted symbol is assumed to be out of
a fixed alphabet Σ. The protocol runs for N rounds (also called the length of the protocol), after
which the parties give output. An instance of the protocol, on inputs x, y is said to be correct if
both parties output f (x, y) at the end of the protocol.
In this work we focus on alternating protocols, where as long as there is no noise, the protocol
runs for 2N rounds in which Alice and Bob send symbols alternately. In the presence of ρ-fraction of
edit corruptions (i.e., at most 2ρN insertion/deletion errors), it is possible that some party receives
only N (1 − 2ρ) symbols throughout the protocol. We say that the protocol is correct in presence of
ρ-fraction of edit corruption if both parties output f (x, y) by round N (1 − 2ρ) (according to their
own round counting, which may differ from the count of the other party).
Definition 2.3 (String Matching). We say that τ = (τ1 , τ2 ) is a string matching between a sent
message sm and a received message rm (denoted τ : sm → rm), if |τ1 | = |τ2 |, del(τ1 ) = sm,
del(τ2 ) = rm, and τ1 [i] ≈ τ2 [i] for all i = 1, . . . , |τ1 |. Here del is a function that deletes all the ∗’s
in the string and two characters a and b satisfy a ≈ b if a = b or one of a and b is ∗. We assume
that ∗ is a special symbol that does not appear in sm and rm.
Definition 2.4 (Edit Distance). The edit distance of between sm ∈ Σ∗ and rm ∈ Σ∗ is defined as
ED(sm, rm) = minτ :sm→rm sc(τ1 ) + sc(τ2 ). Here sc(τ1 ) is the number of ∗’s in τ1 .
Fact 2.5 (Triangle Inequality). For any three strings x, y, z, ED(x, y) ≤ ED(x, z) + ED(y, z).
Fact 2.6. For any two strings x, y, ED(x, y) = |x| + |y| − 2 · LCS(x, y). Here LCS(x, y) is the
longest common substring of x and y.
6

Lemma 2.7. Let x ∈ Σm be some given string, m ≥ n and |Σ| ≥ 4. For any constant α ∈ [0, 1],
P ry←Σn [ED(x, y) ≤ α · m] ≤ |Σ|−

(1−α)m
2

.

U

Proof. By Fact 2.6, we know that ED(x, y) ≤ α · m ⇔ LCS(x, y) ≥ n+(1−α)m
. If we want to upper
2
n+(1−α)m
n
, we can
bound the number of y ∈ Σ such that LCS(x, y) ≥
2
i
h just enumerate locations
of the common substring. Then, Pry←Σn [ED(x, y) ≤ α · m] = Pry←Σn LCS(x, y) ≥
U
U

(1−α)m
Pn
n
− n+(1−α)m
−
n−l
n
n
2
2
/|Σ| ≤ 2 · |Σ|
≤ |Σ|
.
n+(1−α)m
l |Σ|
l=

n+(1−α)m
2

≤

2

3

Edit-distance tree code

In this section we recall the notion of tree-codes [28] and provide a novel primitive, namely, the
edit-distance tree-code.
Definition 3.1 (Prefix Code). A prefix code C : Σnin → Σnout is a code such that C(x)[i] only
depends on x[1..i]. C can be also considered as a |Σin |-ary tree of depth n with symbols written
on edges of the tree using an alphabet size |Σout |. On this tree, each tree path from the root of
length l corresponds to a string x ∈ Σlin and the symbol written on the deepest edge of this path
corresponds to C(x)[l].
Definition 3.2 (α-bad Lambda). We say that a prefix code C contains an α-bad lambda if when
you consider this prefix code as a tree, there exist four tree nodes A,B,D,E such that B 6= D,
B 6= E, B is D and E’s common ancestor, A is B’s ancestor or B itself, and ED(AD, BE) ≤
α · max(|AD|, |BE|). Here AD and BE are strings of symbols along the tree path from A to D
and the tree path from B to E. See Figure 2 for an illustration.
Definition 3.3 (Edit-distance Tree Code). We say that a prefix code C: Σnin → Σnout is a α-editdistance tree code if C does not contain an α-bad lambda.
Our main theorem in this section is the existence of edit-distance tree codes,
Theorem 3.4. For any d ≥ 2, n > 0 and 0 < α < 1, there exists an α-edit-distance tree code of
depth n with alphabet size |Σin | = d and |Σout | = (176 · d)4/(1−α) .
Proof. We prove this theorem by induction on n. To this end we define a slightly stronger notion
than α-bad lambda free, which we call “excellent”. Intuitively, if a tree-code C is excellent, then
with a good probability, C will not cause a bad lambda in a tree-code that contains C as a subtree.
This would allow us to construct lambda-free trees of length n building on lambda-free trees with
a smaller depth as subtrees.
Definition 3.5 (Potential Probability). For any prefix code C : Σnin → Σnout , and any i ≥ 0,
consider C as a tree and define a new (non-regular) tree C ′ by connecting a simple path of length i
to the root of C, making the other end of this path the root of C ′ . Label each edge along the new
path with a symbol from Σout chosen uniformly and independently.
The potential probability Pi (C) is defined as the probability that the new tree C ′ has a α-bad
lambda with A = the root of C ′ and B = the root of C. See Figure 3 for an illustration.
Definition 3.6 (Excellent). For a constant c1 > 1, which we will fix shortly, we say that a prefix
code C is excellent if ∀i ≥ 0, Pi (C) · (d · c1 )i < 1 and C is α-bad-lambda-free.
7

In the proof, we are going to construct a set called Sn which would contain only excellent d-ary
prefix codes of depth n with alphabet size dOα (1) . Since excellent is a stronger notion than α-bad
lambda-free, if we can construct Sn and show that for any n > 0 it is non-empty, then we are
done. In each Sn , all codes use the same Σin and Σout . We have |Σin | = d and |Σout | = swhere the
conditions we put on s thorough the following proof are given by:


α
4
4
4d
αd
2
· (d · c1 ) 1−α + 1, d , ( ) 1−α , (c1 · d · 4) 1−α .
s = max
(1 − α)
c2
Here c1 = 44, and c2 =

1
11 .

Therefore, taking s ≥ (176d)4/(1−α) satisfies all the above conditions.

Let us now inductively construct Sn . For notation convenience, let S0 = {a single node}. For
n > 0, let




σ


σ1
d






σ2
T1 , T2 , ..., Td ∈ Sn−1 and σ1 , σ2 , ..., σd ∈ Σout .
S̃n = T =




···






Td
T1
T2

and define Sn = {C ∈ S̃n | C is excellet}. From this definition, we directly have that every C ∈ Sn
is excellent, and we are only left to show that Sn is non-empty. Actually, we are going to prove the
following claim by induction.
Claim 3.7. For all n,

|Sn |
|S̃n |

≥ c2 =

1
11 .

Base case (n = 1): Consider the following set.
S1′ = {C | C is a d-ary prefix code of depth 1 and d different codewords}
We want to show that S1′ ⊆ S1 . For any C ∈ S1′ , it is clear that C does not have any α-bad lambda.
Because in this depth 1 tree, one can only pick A = B to be the root, and D, E to be some different
leaves. Then ED(AD, BE) = 2 and |AD| = |BE| = 1. So ED(AD, BE) > α · max(|AD|, |BE|).
Now let’s consider the potential probability Pi (C). Suppose there exists an α-bad lambda in the
tree after adding a path of length i. Then in this α-bad lambda, B is the original root, AB is the
path added to the root and D and E are two different leaves of the tree. There are two cases to
consider:
1
> α.
1. i = |AB| > α/(1 − α): In this case, since |BE| = 1, (|AD| − |BE|)/|AD| = 1 − 1+|AB|
So it is not possible that ED(AD, BE) < α · |AD|. Thus Pi (C) = 0.
2. i = |AB| ≤ α/(1−α): In this case, let W be the event that one of the labels along the path AB
equals to one of the d codewords of C. Clearly, when W does not happen, ED(AD, BE) =
α
αd
·(d·c1 ) 1−α ,
|AD|+|BE| > α·|AD|. It is also immediate that Pr[W ] ≤ i· ds . We require s > (1−α)

and get that Pi (C) · (d · c1 )i ≤ Pr[W ] · (d · c1 )i ≤

αd
(1−α)s

α

· (d · c1 ) 1−α < 1.

Therefore, we have proved that all the prefix codes in S1′ are excellent and therefore in S1 . Then
|S1′ |
1|
≥ (1 − 1/d)d > 1/11 = c2 .
because s ≥ d2 , we get |S
≥
= s(s−1)×···×(s−d+1)
sd
|S̃ |
|S̃ |
1

1

8

Inductive step: Suppose we already know that for 1 ≤ i < n,

|Si |
|S̃i |

≥ c2 , and let us prove that

|Sn |
|S̃n |

≥ c2 . We will use the following lemma, whose proof is quite straightforward and can be found
in Appendix B.
Lemma 3.8. If for all 1 ≤ i < n,

|Si |
|S̃i |

≥ c2 . Then for any x ∈ Σjout where 0 < j ≤ n and y ∈ Σnin ,

−j
it holds that PrC←S̃n [C(y)[1..j] = x] ≤ c1−j
2 s .
U

n|
≥ c2 , we can choose C randomly from S̃n , and show that Pr[C is excellent] ≥ c2 .
In order to show that |S
|S̃n |
To this end, consider the conditions of being excellent in turn:

1. Let’s first consider Pr[Pi (C) · (d · c1 )i ≥ 1]. By Lemma 3.8 and Lemma 2.7, we get

≤

EC←S̃n [Pi (C)]
U
X
X

Pr [ED(z ◦ C(x), C(y)) ≤ α · max(i + n1 , n2 )]

z←Σi
1≤n1 ,n2 ≤n x∈Σn1 ,y∈Σn2 , U out
in
in
C←S̃n
x[1]6=y[1]
U

X

≤

n1 +n2

d

1 −n2
· c2−n
2

1≤n1 ,n2 ≤n

n

Prn

1 , y←Σ 2 , z←Σi
x←Σout
out
out
U

U

[ED(z ◦ x, y) ≤ α · max(i + n1 , n2 )]

U

n1 +n2



n1 +n2 +i
d
d − 1−α n1 +n2 − (1−α)i
− 1−α
·
2
4
≤
s 2
·s 4
≤
s
c2
c2
1≤n1 ,n2 ≤n
1≤n1 ,n2 ≤n
∞
X
X  1 n1 +n2
j
7
≤
(c1 · d · 4)−i
· (c1 · d · 4)−i =
(c1 · d · 4)−i ≤
4
4j
36


X

1≤n1 ,n2 ≤n

X

j=2

By Markov’s inequality, Pr[Pi (C) · (d · c1 )i ≥ 1] ≤
1−c2
5
7 P∞ 1
7
i=0 4i = 27 < 11 = 2 .
36

7
36

· 41i . Then

P∞

i
i=0 Pr[Pi (C) · (d · c1 )

≥ 1] ≤

2. Now let’s consider the event that C has an α-bad lambda with A = B = root. It is easy to
see that this event is equivalent to P0 (C) ≥ 1. Therefore it is covered by the previous case.
3. Now let’s consider the event that C has an α-bad lambda with A = root and B 6= root. By
Lemma 3.8 and Definition 3.6, we have
P r[C has an α-bad lambda with A = root, B 6= root]
∞
∞
X
X
X
1
5
1 − c2
1
1 n1
1−n1
n1
−n1
) =
=
.
( )n1 = <
≤
d · c2
· (d · c1 )
≤
(
c c
4
3
11
2
n =1
n =1 1 2
n1 ≤n

1

1

4. Finally let’s consider the case that C has an α-bad lambda with A 6= root. It is easy to see
that this event never happens because C’s subtrees rooted at depth 1 in C are all excellent.
Therefore by union bound, Pr[C is excellent] is at least
≥1 −

∞
X

Pr[Pi (C) · (d · c1 )i ≥ 1] − Pr[C has an α-bad lambda with A = root, B 6= root]

i=0

≥1 −

1 − c2 1 − c2
−
= c2 .
2
2
9

3.1

Decoding of edit-distance tree codes

The decoding of a codeword rm ∈ Σjout via an edit-distance tree-code C amounts to finding a message whose encoding minimizes the suffix distance to rm, i.e., DEC(rm) = arg minm∈Σ≤n SD(rm, C(m)),
in
where the suffix distance SD(·, ·) is defined as follows.
Definition 3.9 (Suffix Distance). Given any two strings sm, rm ∈ Σ∗ , the suffix distance between
|τ1 | sc(τ1 [i..|τ1 |])+sc(τ2 [i..|τ2 |])
sm and rm is SD(sm, rm) = minτ :sm→rm maxi=1
|τ1 |−i+1−sc(τ1 [i..|τ1 |]) .
The following lemma, which plays an important role in the analysis of the simulation protocols
that we present in the next sections, shows that if a message sm is encoded by some α-edit-distance
tree code and the received message rm satisfies SD(sm, rm) ≤ α2 , then the receiver can recover the
entire sent message correctly.
Lemma 3.10. Let C: Σnin → Σnout be an α-edit-distance tree code, and let rm ∈ Σm
out (m can be
different from n). There exists at most one sm ∈ ∪ni=1 C(Σnin )[1..i] such that SD(sm, rm) ≤ α2 .
The proof appears in Appendix B.

4

A coding scheme with a polynomial alphabet size

In this section, we show a protocol π that solves P JP (T ) in O(T ) rounds over channels with
alphabet size poly(T ), and is resilient to (a constant fraction of) insertion/deletion errors. Since
the P JP (T ) is complete for interactive communication, this implies that any binary protocol with
T rounds can be simulated in O(T ) rounds over a channel with polynomially-large alphabet that
corrupts at most a fraction 1/18 − ε of the transmissions. While this protocol does not exhibit a
constant rate, it contains all the main ideas for the constant-rate protocol of Theorem 1.4, and thus
we focus on this simple variant first. Then, in Section D we discuss how to reduce the alphabet size
and achieve a protocol with O(T ) communication complexity with the same resilience guarantees.
Assume π has 2N alternating rounds, that is, Alice and Bob send N symbols each, assuming
there are no errors. We would like the protocol to resist a fraction of ρ edit-corruptions, that is,
the protocol should succeed as long as there are at most 2ρN insertion/deletion errors. Due our
assumption that the adversary never causes the protocol to “get stuck”, this amounts to at most
2ρN deletions, where each deletion is followed by an insertion.
N
We assume that Alice and Bob share some fixed α-edit-distance tree code C : ΣN
in → Σout given
by Theorem 3.4. We will set the values of N , α, and Σin later. Currently we only need to know
N = poly(T ).
Let us begin with a high-level outline of the protocol π. The protocol basically progresses by
sending edges in the tree T of the underlying P JP (T ), interactively constructing the joint path
(similar to [7]). To communicate an edge e, the parties encode it as a pair of numbers (n, s), where
0 ≤ n ≤ N and s ∈ {1, 2, 3, 4}. The value n indicates the number of some previous round in which
some edge e′ was sent, and the value s determines e as the s-grandchild of e′ . That is, we always
send an edge e by linking it to an edge e′ that was previously sent, such that e′ is located two levels
above in unique path leading from the root to e. If e does not have a grandparent (e.g., it is the
at the first or second level in T ), we will set n = 0. Sometimes the parties have no edge to send,
in which case they set n = N and say that e is an empty edge. We take Σin to be all the possible
10

encodings (n, s). As 0 ≤ n ≤ N and 1 ≤ s ≤ 4, we have |Σin | = poly(N ) = poly(T ). As |Σout | is
polynomial in |Σin | (Theorem 3.4), we also have |Σout | = poly(N ) = poly(T ).
The protocol π is described in Protocol 1. The description is for Alice side; Bob’s part is
symmetric. Here we explain more than the pseudocode on how to get E(dA ). Basically dA is a
string of symbols in Σin and those symbols are in the form (n, s). E(dA ) will be the set of edges
these symbols in dA represent. To get the edge each symbol (n, s) represents, we will first find the
edge sent in n-th round and get its proper grandchild according to s. If n is not in the correct
range then we consider dA as not valid.
Protocol 1 The protocol π
Let T be given by P JP (T ). Recall that Alice’s input is X. Assume the parties share some fixed α-editN
distance tree code C : ΣN
in → Σout .
Initially we set the counter i = 0. For any leaf node v in T we initialize a counter s(v) = 0. Run the following
for N times.
1.
2.
3.
4.

i ← i + 1.
Receive a symbol rA [i] from the other party. (For Alice, if i = 1, skip this step)
Find dA ∈ Σ∗in which minimizes SD(dA , rA [1...i]).
If E(dA ) ∪ X has a unique path from the root in T , do the following. Here E(dA ) is the set of edges
indicated by dA , if dA is not a valid string of symbols, E(dA ) = ∅.

(a) If this path reaches a leaf node v, then s(v) ← s(v) + 1.
(b) Let e be the deepest edge on the the unique path from root. If e ∈ X , and e is either an edge
in the first or second level of T or e’s grandparent has been sent, set sA [i] to be encoding of e,
otherwise set sA [i] to be encoding of an empty edge.
5. If E(dA ) ∪ X does not have a unique path from the root in T , set sA [i] to be encoding of an empty
edge.
6. If i = N (1 − 2ρ), output the leaf node v with the largest s(v).
7. Send C(sA [1...i])[i] to Bob.

We now analyze Protocol 1 and prove it resists up to (1/18 − ε)-fraction of edit corruptions.
Let NA and NB be the counter i of Alice and Bob respectively, when one of them reaches the
end of the protocol π. Let τA = (τ1 , τ2 ) be the string matching between sB [1..NB ] and rA [1..NA ]
that is consistent with the protocol. Let τB = (τ3 , τ4 ) be the string matching between sA [1..NA ]
and rB [1..NB ]. Recall that we use sc(τ ) to denote the number of ∗’s in the string. By definition,
sc(τ1 ) + sc(τ3 ) ≤ 2ρN and sc(τ2 ) + sc(τ4 ) ≤ 2ρN .
In the analysis we count the number of rounds in which Alice correctly decodes the entire
(current) set of edges sent by Bob. We call each such round a good decoding.
Definition 4.1 (Good Decoding). When a party decodes a message, we say it is a good decoding if
the decoded messages is exactly the one sent by the other side (i.e., dA = sB [1..i] or dB = sA [1..i],
assuming the other side is at round i), and the symbol just received is not an adversarial insertion.
If a decoding is not good, we call it a bad decoding.
In the following lemma we show relate the number of good decodings to the noise, and show
that as long as noise is small enough, there will be many rounds with good decodings. The proof
can be found in appendix C.
Lemma 4.2. Alice has at least NA + (1 − α2 )sc(τ2 ) − (1 + α2 )sc(τ1 ) good decodings. Bob has at least
NB + (1 − α2 )sc(τ4 ) − (1 + α2 )sc(τ3 ) good decodings.
11

After we have established that Alice and Bob will have many good decodings, we show that this
implies they will have good progress in constructing their joint path in the underlying P JP (T ).
Consider the NA + NB decodings that happen during the protocol, and sort them in a natural
order; we say that these decodings occur at “times” t = 1, 2, . . . , NA + NB . Note that the decodings
need not be alternating — Eve’s insertions and deletions may cause one party to perform several
consecutive decodings while the other party does not receive any symbol, and performs no decoding.
We also assume that for each decoding, the sending of the next symbol happens at the same “time”
as the decoding. Let eA (t) be the set of edges Alice has sent at time t and eB (t) be the set of edges
Bob has sent at time t. Let P be the correct path of length T of P JP (T ). Define l(t) to be the
length of the longest path from the root using edges in P ∩ (eA (t) ∪ eB (t)). Basically l(t) measures
how much progress Alice and Bob have made. Let us also define m(i) to be the first time t such
that l(t) ≥ i. For notation convenience, let m(0) = 0.
The following lemma shows that if the parties do not make progress, many bad decodings (and
thus, many errors) must have occurred. The proof can be found in appendix C.
Lemma 4.3. For i = 0, ..., T − 1, if m(i + 1) 6= m(i) + 1, then during time m(i) + 1, ..., m(i + 1) − 1,
the following is true.
1. If
is
2. If
is

i is odd, then there are no good decodings of Bob. The number of good decodings of Alice
at most the number of bad decodings of Bob.
i is even, then there are no good decodings of Alice. The number of good decodings of Bob
at most the number of bad decodings of Alice.

Combining the above lemmas, we get the main theorem for protocols with polynomial size
alphabet.
T
⌉, and a (1 − ε)-edit tree
Theorem 4.4. For any ε > 0, the protocl π of Protocol 1 with N = ⌈ 16ε
code, solves P JP (T ) and is resilient to a (1/18 − ε)-fraction of edit corruptions.
1
−ε and α = 1−ε. Let gA be the number of good decodings of Alice, bA = NA −gA
Proof. Set ρ = 18
be the number of bad decodings of Alice. Similarly, let gB be the number of good decodings of Bob,
and let bB = NB − gb . Recall that sc(τ1 ) + sc(τ3 ) = sc(τ2 ) + sc(τ4 ) ≤ 2ρN , then by Lemma 4.2, we
have

2
2
(sc(τ1 ) + sc(τ2 )) + sc(τ1 ) − sc(τ2 ) + (sc(τ3 ) + sc(τ4 )) + sc(τ3 ) − sc(τ4 )
α
α
8ρN
.
≤
α

bA + bB ≤

Then we have,
8ρN
8ρN
≥ (NA − N (1 − 2ρ)) + N (1 − 2ρ) −
α
α
8ρN
8ρN
− (NA − N (1 − 2ρ)) + N (1 − 2ρ) +
≥ bA + bB −
α
α
= bA + bB + (NA − N (1 − 2ρ)) + N (1 − 16ρ/α − 2ρ)

gA = NA − bA ≥ NA −

> bA + bB + (NA − N (1 − 2ρ)) + N (1 − (1 − 18ε)(1 + 2ε))
≥ bA + bB + (NA − N (1 − 2ρ)) + 16εN ≥ bA + bB + (NA − N (1 − 2ρ)) + T.
12

Similarly we have gB > bA + bB + (NB − N (1 − 2ρ)) + T .
Using Lemma 4.3 we deduce that by time m(T ) the number of good decodings Alice may have
is bounded by T + bB . From this point and on, every good decoding at Alice’s side adds one vote
for the correct leaf, making at least gA − (T + bB ) > bA + (NA − N (1 − 2ρ)) votes for that node
by the end of the protocol, and at least bA + 1 votes until Alice reaches round N (1 − 2ρ) when
she gives her output. On the other hand, any wrong output can get at most bA votes, thus Alice
outputs the correct leaf node at round N (1 − 2ρ). By a similar reasoning, Bob also outputs the
correct leaf node when he reaches round N (1 − 2ρ).

5

A coding scheme with a constant alphabet size

Based on the protocol in Section 4, with some modifications, we obtain a protocol that has a
constant size alphabet and a constant rate. To this end, we show how to encode each edge using
varying-length encoding over a constant size alphabet. Although substantially more technically
involved, this protocol is quite a straightforward extension of the protocol presented above. We
thus defer the detailed analysis of this protocol to Appendix D.
Theorem 5.1. For any ε > 0, the simulation π ′ of Protocol 2 with N = ⌈ εT2 ⌉, and a (1 − ε)-edit
distance tree code, solves P JP (T ) and is resilient to a (1/18 − ε)-fraction of edit corruptions.
Since P JP (T ) is complete for interactive communication, the above theorem proves Theorem 1.4.

References
[1] Shweta Agrawal, Ran Gelles, and Amit Sahai. Adaptive protocols for interactive communication. arXiv preprint arXiv:1312.4182, 2013.
[2] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost
k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.
[3] Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise.
In Foundations of Computer Science, IEEE Annual Symposium on, pages 160–166. IEEE
Computer Society, 2012.
[4] Zvika Brakerski, Yael Tauman Kalai, and Moni Naor. Fast interactive coding against adversarial noise. J. ACM, 61(6):35:1–35:30, December 2014.
[5] Zvika Brakerski and Moni Naor. Fast algorithms for interactive coding. In SODA ’13: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 443–456,
2013.
[6] Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, and Falk Unger. Noisy interactive
quantum communication. In 55th IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 296–305, 2014.
[7] M. Braverman and A. Rao. Toward coding for maximum errors in interactive communication.
Information Theory, IEEE Transactions on, 60(11):7248–7255, Nov 2014.

13

[8] Mark Braverman and Klim Efremenko. List and unique coding for interactive communication
in the presence of adversarial noise. In Foundations of Computer Science (FOCS), IEEE 55th
Annual Symposium on, pages 236–245, 2014.
[9] Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In STOC ’11: Proceedings of the 43rd annual ACM symposium on Theory of
Computing, pages 159–166, New York, NY, USA, 2011. ACM.
[10] Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Maximal noise in interactive communication over erasure channels and channels with feedback. In Proceedings of the 2015 Conference
on Innovations in Theoretical Computer Science, ITCS ’15, pages 11–20, New York, NY, USA,
2015. ACM.
[11] Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal coding
for streaming authentication and interactive communication. In Ran Canetti and Juan A.
Garay, editors, CRYPTO ’13, volume 8043 of LNCS, pages 258–276. Springer Berlin, 2013.
[12] Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal coding for streaming authentication and interactive communication. Information Theory, IEEE
Transactions on, 61(1):133–145, Jan 2015.
[13] Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels and channels with feedback. In Proceedings of the 26th Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA ’15, pages 1296–1311, 2015.
[14] Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient and explicit coding for interactive communication. In Foundations of Computer Science, 2011 IEEE 52nd Annual Symposium on,
pages 768–777. IEEE Computer Society, 2011.
[15] Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication.
Information Theory, IEEE Transactions on, 60(3):1899–1913, March 2014.
[16] Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II:
Efficiency and List Decoding. In Foundations of Computer Science (FOCS), IEEE 55th Annual
Symposium on, pages 394–403, 2014.
[17] Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive
coding I: Adaptivity and other settings. In STOC ’14: Proceedings of the 46th Annual ACM
Symposium on Theory of Computing, pages 794–803, 2014.
[18] Bernhard Haeupler. Interactive channel capacity revisited. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 226–235, 2014.
[19] J. Justesen. Class of constructive asymptotically good algebraic codes. Information Theory,
IEEE Transactions on, 18(5):652–656, Sep 1972.
[20] Gillat Kol and Ran Raz. Interactive channel capacity. In STOC ’13: Proceedings of the 45th
annual ACM Symposium on theory of computing, pages 715–724, 2013.
[21] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press,
1997.
14

[22] Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals.
In Soviet physics doklady, volume 10, page 707, 1966.
[23] R. Ostrovsky, Y. Rabani, and L.J. Schulman. Error-correcting codes for automatic control.
Information Theory, IEEE Transactions on, 55(7):2931–2941, July 2009.
[24] Rafail Ostrovsky, Yuval Rabani, and Leonard J. Schulman. Error-correcting codes for automatic control. In Foundations of Computer Science, Annual IEEE Symposium on, pages
309–316. IEEE Computer Society, 2005.
[25] L. J. Schulman. Communication on noisy channels: a coding theorem for computation. Foundations of Computer Science, Annual IEEE Symposium on, pages 724–733, 1992.
[26] L. J. Schulman and D. Zuckerman. Asymptotically good codes correcting insertions, deletions,
and transpositions. Information Theory, IEEE Transactions on, 45(7):2552–2557, Nov 1999.
[27] Leonard J. Schulman. Deterministic coding for interactive communication. In STOC ’93:
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 747–
756, New York, NY, USA, 1993. ACM.
[28] Leonard J. Schulman. Coding for interactive communication. IEEE Trans. Inf. Theory,
42(6):1745–1756, 1996.

A

More details about the noise model

Here we give some justifications that explains our modeling choices, and show it is weak enough to
be a reasonable (i.e., non-trivial) model, yet strong enough to generalize other natural models.
As explained above, there are two main paradigms for distributed protocols in the asynchronous
setting.
1. Message-driven model: In this model, each party wakes up and replies only when received
a message. If several event occur “simultaneously”, we assume a worst-case scenario in which
the adversary determines the order of events. We show that allowing arbitrary noise patterns
make the protocol too strong. Either it halts in the middle, or the noise pattern limits the
amount of interaction between the two parties.
(a) If a deletion occurs (without being followed by a insertion, as in our model), then both
parties clearly get stuck. More generally, it follows that at any point of the protocol,
the number of insertions must exceed the number of deletions. We now show that this
restriction still yields a too strong noise model which doesn’t allow any resilient-protocols.
(b) Assume the adversary is allowed to make up to N/c insertions anywhere during the
protocol. We show that this limits the protocol to performing c + 1 interactions between Alice and Bob (where each “interaction” is sending a message of arbitrary length,
which is depends on messages received in prior interactions). It then follows that one
cannot obtain a constant-rate resilient protocol that withstands a constant fraction of
noise c, as limiting the number of interactions may cause an exponential increase in the
communication [21].

15

Claim A.1. Suppose Alice and Bob each send N symbols in total and the adversary can
make up to N/c insertion/deletion errors. Then the adversary can make Alice and Bob
have at most c + 1 interactive rounds (alternations).
Proof. Without the loss of generality, let’s assume Alice speaks first. The adversary
makes the following attack:
i. After Alice sends Bob a symbol, the adversary inserts N/c symbols from Alice to
Bob.
ii. Bob receives all the 1 + N/c symbols and replies all of them (recall, each incoming
message triggers Bob to a single reply). The adversary guarantees that the order
of event is such that first Bob answers on all messages and only then Alice receives
them (these events are simultaneous, so Eve gets to decide their internal order).
iii. Alice receives all the N/c + 1 bits and replies all of them, one by one. Again, Eve
sets the internal order of events so that first Alice replies all messages before Bob
start replying.
iv. Keep doing this until N symbols are sent by both parties.
It’s easy to see that the protocol has at most c + 1 interactive rounds, where each
interaction contains N/c symbols which can be dependent on previous blocks.
2. Clock-driven model: In this model, each party has a clock and the party wakes up only
when its clock ticks. The parties’ clocks are not assumed to be synchronized or correlated in
any way. We need to carefully describe what happens when the clock ticks is not alternating:
(a) If a party wakes up and there’s no incoming message, then we take a worst case assumption and allow the adversary to set the message that party sees.
(b) If a party wakes up, and more than a single message was sent to him during that time, we
will take a worst-case assumption that the party only sees the last incoming message.1
The following claim shows that the above model can be reduced to the model of editcorruptions we use in this paper.
Claim A.2. The above clock-driven model can be reduced to a message-driven setting with
edit corruptions. That is, any protocol in our model that is resilient to εN edit corruptions,
is also a resilient protocol in the clock-driven setting, which is resilient to up to εN “nonalternating” clock-ticks. A clock tick is considered not alternating if the previous clock tick
belongs to the same same party.
Proof. If there are two clock ticks made by the same party. Without loss of the generality,
let’s assume they are made by Alice. Denote these two clock ticks as A(1) and A(2), and
assume that Bob’s clock ticks after A(2). From Bob’s view, he sees only the message Alice
sends at A(2), so Alice’s first message is deleted. When Alice wakes up at A(2), which follows
the time A(2) (i.e., there is no other events in between), her incoming message queue is empty,
so the adversary determines the symbol she sees; this is exactly an insertion. It follows that
the above non-alternating clock-tick causes exactly the same effect as of a deletion followed
by an insertion. It is easy to verify that multiple non-alternating ticks have the same affect
as multiple edit-corruptions.
1

We show a positive result for this setting, i.e., a resilient protocol. Thus it is better to take worst-case assumptions,
as relaxing them may only get better resilience.

16

B

Missing proofs of Section 3

Proof of Lemnma 3.8. By the way we construct S̃n based on of Sn−1 , and using the fact that for
i < n, ||SS̃i || ≥ c2 , we have
i

Pr [C(y)[1..j] = x] = s−1 ·
C←S̃n

Pr

C←Sn−1

[C(y)[2...j] = x[2..j]]

U

U

≤ s−1 · c−1
2 ·

Pr

[C(y)[2...j] = x[2..j]]

C←S̃n−1
U

..
.
≤ s−j+1 c21−j

Pr

[C(y)[j] = x[j]]

C←S̃n−j+1
U

=

s−j c21−j .

Proof of Lemnma P
3.10. We prove the lemma by contradiction. Suppose there exist two messages
′
n
sm, sm ∈ ∪i=1 C( nin )[1..i] such that both SD(sm, rm) ≤ α2 and SD(sm′ , rm) ≤ α2 . We are going
to show that this results in an α-bad lambda.
Consider the tree of the edit-distance tree code C. Let D and E be the tree nodes such that
the path from root to D denotes message sm and the path from root to E denotes message sm′ .
Let B be the common ancestor of D and E in the tree.
Let τ and τ ′ be the string matching chosen in SD(sm, rm) and SD(sm′ , rm). Let l = |τ1 | and
l′ = |τ1′ |. Choose i, i′ such that del(τ1 [i..l]) = BD and del(τ1′ [i′ ..l′ ]) = BE. Next, consider the
strings del(τ2 [i..l]) and del(τ2′ [i′ ...l′ ]). Both of them are suffixes of rm. Without loss of generality,
let’s assume |del(τ2 [i..l])| ≤ |del(τ2′ [i′ ..l′ ])|. Therefore del(τ2 [i..l]) is also a suffix of del(τ2′ [i′ ...l′ ]) and
there exists j ≤ i such that del(τ2 [j..l]) = del(τ2′ [i′ ...l′ ]). Now consider del(τ1 [j...l]). Since j ≤ i,
del(τ1 [i...l]) is a suffix of del(τ1 [j...l]). So there is a node A which is B’s ancestor or B itself such
that AD corresponds to del(τ1 [j...l]).
Now we have
ED(AD, del(τ2 [j..l])) ≤ sc(τ1 [j..l]) + sc(τ2 [j...l])
sc(τ1 [j..l]) + sc(τ2 [j..l])
· (l − j + 1 − sc(τ1 [j..l]))
=
l − j + 1 − sc(τ1 [j..l])
≤ SD(sm, rm) · |AD|
α
· |AD|.
≤
2
Similarly, we have

α
· |BE|.
2
Since del(τ2 [j..l]) = del(τ2′ [i′ ..l′ ]) and by Fact 2.5, we have
ED(BE, del(τ2′ [i′ ..l′ ])) ≤

ED(AD, BE) ≤ ED(AD, del(τ2 [j..l])) + ED(BE, del(τ2′ [i′ ..l′ ]))
α(|AD| + |BE|)
≤ α · max(|AD|, |BE|).
≤
2
17

This shows that there’s an α-bad lambda in the tree code and therefore we get a contradiction.

C

Missing proofs of Section 4

Proof of Lemnma 4.2. We prove the lemma for Alice, the lemma holds for Bob for the same reason.
Consider the following procedure on the string matching τA = (τ1 , τ2 ):
1. Set t = |τ2 |.
2. While t 6= 0 do
(a) If τ2 [t] = ∗, then mark t as bad and set t ← t − 1.
1 [i..t])+sc(τ2 [i..t])
(b) Elseif maxti=1 sc(τ
≥ α2 , then
t−i+1−sc(τ1 [i..t])

1 [i..t])+sc(τ2 [i..t])
′
′
Let t′ = arg maxti=1 sc(τ
t−i+1−sc(τ1 [i..t]) . Mark t ...t as bad, and set t ← t − 1.
(c) Else mark t as good and set t ← t − 1.

First, we claim that the number of bad t’s is bounded by α2 (sc(τ1 ) + sc(τ2 )) + sc(τ1 ). The reason
is the following: In the above procedure, only step (a) and step (b) can mark some t’s as bad. Each
′
′
1 [t ..t])+sc(τ2 [t ..t])
time we mark t′ ..t as bad (even if t′ = t, e.g., by step (a)), then we know that sc(τ
t−t′ +1−sc(τ1 [t′ ..t]) ≥
2
α
′
′
′
′
2 . So the number of bad t’s among t ..t is bounded by α (sc(τ1 [t ..t]) + sc(τ2 [t ..t])) + sc(τ1 [t ..t]).
Therefore, summing over all intervals t′ ..t that were marked bad, the total amount of bad t’s is
bounded by α2 (sc(τ1 ) + sc(τ2 )) + sc(τ1 ).
Next, we claim that the number of good decodings is at least the number of good t’s. This
implies that for Alice, the number of good decodings is NA + sc(τ2 ) − α2 (sc(τ1 ) + sc(τ2 )) − sc(τ1 )
since the number of good t’s is equal to the length of τ1 , NA + sc(τ2 ), minus the number of bad
t’s, α2 (sc(τ1 ) + sc(τ2 )) − sc(τ1 ). The claim holds since each good t corresponds to a time that Alice
receives some message from Bob and the suffix distance between the message Bob sent and the
1 [i..t])+sc(τ2 [i..t])
message Alice received is at most maxti=1 sc(τ
< α2 . By Lemma 3.10, we know at
t−i+1−sc(τ1 [i..t])
that time the message Bob sent is the only one that has suffix distance less than α2 with respect to
Alice’s received word. So at that time, Alice decodes correctly.
Proof of Lemnma 4.3. We will only prove the lemma for odd i’s. The lemma for even i’s will
follow for the same reason. At time m(i), Alice sends the i-th edge on P . Then during times
m(i) + 1, . . . , m(i + 1) − 1, there are no good decodings of Bob. Otherwise Bob would decode
correctly and send the i + 1-th edge on P . So during times m(i) + 1, ..., m(i + 1) − 1, all the good
decodings are Alice’s. Notice that for each good decoding that happens at Alice’s side, at that
very same time Alice receives a symbol that was sent by Bob (and not a symbol inserted by the
adversary). Recall that Bob sends a symbol only after he performs a decoding, hence, prior to
each good decoding of Alice, there must be a decoding at Bob’s side. However, there are no good
decodings of Bob during this time period. Also at time m(i), the decoding is a decoding of Alice.
So in the time period m(i) + 1, ..., m(i + 1) − 1, the number of good decodings of Alice is at most
the number of bad decodings of Bob.

18

D

Detailed protocol and analysis for Theorem 5.1

In this section we give a protocol π ′ that solves the P JP (T ) task, takes N = Oε (T ) rounds, and is
resilient to (1/18 − ε)-fraction of edit corruptions. In contrast to Protocol 1 presented above, here
π ′ communicates symbols form a constant-size alphabet, and thus has communication complexity
of CC(π ′ ) = Oε (T ), that is, it has constant rate. By this we complete the proof of Theorem 1.4.
The Outline. Generally speaking, π ′ (Protocol 2) follows the same high-level ideas as Protocol 1, except for encoding each edge e transmitted in π via a varying-length binary encoding. More
specifically, each edge e = (n, s) ∈ [T ] × [4] is encoded as the binary description of (i − n, s), where
i is the current round number at the sender’s side. The values n and s have the same meaning as
in Protocol 1: n is a pointer to a previous round number in which the sender started to send an
edge e′ , and s indicates that the new edge e is the s-th grandchild of the edge e′ . An empty edge is
encoded as (0, 0), that is we assume s take values in {0} ∪ [4]. Hence, the above binary description
has length at most log(i − n) + 4 bits. It can be shown that the amortized encoding length, is O(1)
and the proof is similar to the proof in [7].
Several difficulties arise due the above varying-length encoding. First, since the channel’s alphabet has a fixed size, it may take several rounds of communication to transmit a single edge.
Furthermore, during these rounds where e is being transmitted, new symbols are received from the
other side. These symbols may cause the party to understand it needs to send a different edge ẽ,
instead of e that is still in the process of being communicated.
In the case explained above, the party will just add ẽ to a list of edges to be communicated.
Recall that (some of) these edges may be added to the list due to adversarial noise. Moreover,
such “wrong” edges may have a very large encoding (e.g., when the adversary causes a party to
believe it needs to resend the first edge at the middle of the protocol; this has an encoding of length
log(N )). To prevent the adversary from delaying the progress of the protocol by these effects, we
make the party send all the edges in the list in parallel. That is, we cycle through the list of edges
and send one bit from the encoding of any edge of the list. That way, long encodings do not delay
the transmission of other edges. Furthermore, we attach to each edge a “liveliness” counter which
indicates how likely it is for a specific edge to be part of the correct path of the underlying P JP (T ):
each time a new symbol is received and the decoding of the incoming message implies some edge e
should be sent, we increase the liveliness of that edge. This way, if an incorrect edge with a very
long binary encdoing is added to the list, the noise must keep indicating this edge is needed in
order to keep it “alive” in the list.
The Fine Details. We assume alphabet size of |Σin | = O(1/ε2 ). Each party maintains a table (the EdgeTable), that stores all the edges this party is currently communicating. As mentioned
above, the party cycles through the EdgeTable and sends one bit of every edge there. Thus, if
the table holds < 1/ε2 edges, a single round of communication suffices to send one bit of all the
edges. Otherwise, several rounds of communication may be needed. Assume that the table holds
E edges, we name the process of sending each bit of all the E edges, a cycle. Note that a cycle
takes E/(1/ε2 ) rounds of communication; each such round is called a page, and we say that a page
is full if it contains 1/ε2 edges. For simplicity, we assume that new edges are added to the table
only when a cycle is completed. Similarly, edges that were fully communicated are removed from
the table at the end of a cycle.
The EdgeTable contains the following fields:
19

• Edge: contains the edge e in the underlying P JP (T ) tree T .
• Edge Binary Description: contains the varying-length binary description of e, as described
above.
• Current Sent Length: means how many bits of the binary description were already communicated.
• Live Points: A number describing the liveliness of the edge. When e is added to the table it
gets 1/ε live points. At any future round where e is to be added to the table, if it is already
in the table it’s live points increase by 1/ε. Every round we communicate a bit of e its live
points decrease by 1. If the live points of some edge reach 0 at the end of a cycle, the edge is
removed from the table.
Let us now formally define the process of a cycle: transmitting one bit from each edge in
EdgeTable. In fact, along with one bit per edge, we also send some meta-data, which is described
in Procedure 1 below. Each symbol in the our encoding Σin needs to hold 4 bits for up to 1/ε2
edges, thus it is clear that |Σin | = O(1/ε2 ) suffices. We note that the information sent at each cycle
suffices to exactly recover the EdgeTable table at the other side.
Procedure 1 Cycle(EdgeTable)
repeat ⌈E/(1/ε2 )⌉ times (E is the number of edges in EdgeTable):
The next symbol to communicate consists of the following information:
1. One bit to indicate whether this page is the last page in the cycle or not.
2. For each e of the next 1/ε2 edges in E include:
(a) the next bit of e’s “Edge Binary Description” to be transmitted
(b) One bit to indicate whether e has “Live Points” = 0.
(c) One bit to indicate whether e has “Current Sent Length” = the length of its “Edge Binary
Description”.
(d) One bit to indicate whether e was added to the table at the end of the last cycle.

We now describe the UpdateTable(e) procedure. This procedure is called after every cycle, adds
the edge e to the cycle, and removes edges that either were fully transmitted or their “Live points”
has reached 0. The parties add edges to their EdgeTable using the update process UpdateTable(e)
described in Procedure 2.
Procedure 2 UpdateTable(e)
1. Add e:
(a) If e is not an empty edge and e is not in the table, then insert e to the table. Compute the
“Edge Binary Description”. Set “Current Sent Length” = 0 and “Live Points” = 1ε .
(b) If e is not an empty edge and e is in the table, increase its “Live Points” by 1ε .
2. Maintain liveliness, and remove dead edges:
(a) Decrease “Live Points” of each edge in the table by 1. Increase “Current Sent Length” of each
edge in the table by 1.
(b) Remove all the edges with “Live Points” = 0 or “Current Sent Length” = the length of its “Edge
Binary Description”.

20

We are now ready to describe the Protocol π ′ , given in Protocol 2. Similar as in Section 4, we
say that dA is valid if it is the encoding of a set of edges.
Protocol 2 The protocol π ′
Let T be given by P JP (T ). Recall that Alice’s input is X. Assume the parties share some fixed α-editN
distance tree code C : ΣN
in → Σout .
Initialize i = 0.
Repeat for N = ⌈T /ε2 ⌉ times:
1.
2.
3.
4.

i ← i + 1.
Receive a symbol rA [i] from the other party. (For Alice, if i = 1, skip this step)
Find dA ∈ Σ∗in which minimizes SD(dA , rA [1...i]).
If E(dA ) ∪ X has a unique path from the root in P JP (T ), do the following. Here E(dA ) is a set of
edges indicated by dA , if dA is not a valid message, E(dA ) = ∅.
(a) If this path already reach the leaf node v, then s(v) ← s(v) + 1.
(b) Let e be the deepest edge on the the unique path from root. If e 6∈ X , or e is not an edge in the
first or second level of T or e’s grandparent has been sent, set e to be an empty edge.

5.
6.
7.
8.
9.

If E(dA ) ∪ X does not have a unique path from the root in P JP (T ), set e to be an empty edge.
If a cycle is completed (or if i = 1), call UpdateTable(e).
sA [i] ← the next page of Cycle(EdgeTable).
Send C(sA [1...i])[i] to Bob.
If i = N (1 − 2ρ), output the leaf node v with the largest s(v).

We now analyze the coding scheme of Protocol 2, and prove our main theorem (Theorem 1.4,
obtained via Theorem 5.1). First, we claim that Protocol 2 has a constant rate. Indeed, it communicates 2N log |Σout | bits throughout. We use a tree code with |Σin | = Oε (1) and α = 1 − ε and
thus by Theorem 3.4 we get that |Σout | = Oε (1) as well. Hence, the total communication of π is
given by
CC(π ′ ) = 2N log |Σout | = T /ε2 · (1/ε2 )O(1/ε) = Oε (T ).
The correctness analysis is quite similar to the one of Section 4. As above, let NA and NB be
the counter i of Alice and Bob when one of them reaches the end of the protocol. Let τA = (τ1 , τ2 )
be the string matching between sB [1..NB ] and rA [1..NA ] that is consistent with the protocol. Let
τB = (τ3 , τ4 ) be the string matching between sA [1..NA ] and rB [1..NB ]. Recall that we use sc(τ ) to
denote the number of ∗’s in the string. By definition, sc(τ1 ) + sc(τ3 ) ≤ 2ρN and sc(τ2 ) + sc(τ4 ) ≤
2ρN .
Let’s first prove the following lemma which shows that the case where the number of edges in
the table exceeds ε12 is very rare.
Lemma D.1. Alice sends at most ε · NA full pages, and Bob sends at most ε · NB full pages (recall
that a full page is a page that contains ε12 edges).
Proof. We prove the lemma for Alice, and the same holds for Bob. Notice that the sum of “Live
Points” of all edges in the table is always non-negative. And in each round of Alice, if the UpdateTable procedure is called, it increases the sum of “Live Points” by at most 1ε . Whenever Alice
sends a page of ε12 edges, the sum of “Live Points” is decreased by at least ε12 . Alice has NA rounds

21

in total. Let pA be the number of full pages sent by Alice. By a simple counting argument, we have
NA ·

1
1
− pA · 2 ≥ 0.
ε
ε

Therefore pA ≤ ε · NA .
We again define good decoding, which is slightly different from the one of Section 4—we only
care about decodings that happen at the end of a cycle.
Definition D.2 (Good Decoding). When a party decodes a message, we say that it is a good
decoding if the followings hold:
1. The decoding outputs the entire message sent so far by the other side (dA = sB [1..i] or
dB = sA [1..i])
2. The symbol just received was not inserted by the adversary.
3. The party has finished a cycles (i.e., UpdateEdge(e) is called at that round.)
Otherwise we call it a bad decoding.
Lemma D.3. Alice has at least NA (1 − ε) + (1 − α2 )sc(τ2 ) − (1 + α2 )sc(τ1 ) good decodings. Bob has
at least NB (1 − ε) + (1 − α2 )sc(τ4 ) − (1 + α2 )sc(τ3 ) good decodings.
Proof. We prove the lemma for Alice; the lemma for Bob holds for the same reason. By Lemma 4.2,
the number of decodings of Alice which satisfy the first two constraints in Definition D.2 is at
least NA + (1 − α2 )sc(τ2 ) − (1 + α2 )sc(τ1 ). By Lemma D.1, the number of decodings of Alice
which don’t satisfy the third constraint in Definition D.2 is at most ε · NA . So Alice has at least
NA + (1 − α2 )sc(τ2 ) − (1 + α2 )sc(τ1 ) − ε · NA good decodings.
As in the analysis of Protocol 1, we now sort all the good and bad decodings of both Alice and
Bob by the time these decodings happen. Since in total we have NA +NB decodings, we can assume
these decodings happen at times t = 1, 2, ..., NA + NB . Again, we assume that for each decoding,
the sending procedure right after it happens at the same time as the decoding. Let eA (t) be the
set of edges Alice has fully communicated up to time t and eB (t) be the set of edges Bob has fully
communicated up to t. Let P be the correct path of length T defined by the underlying P JP (T ).
Let l(t) be the length of the longest path starting from root using edges from P ∩ (eA (t) ∪ eB (t)).
Basically l(t) measures how much progress Alice and Bob have made. Let’s also define m(i) to be
the first time t such that l(t) ≥ i.
The following lemma is similar to Lemma 4.3 and shows that many bad decodings are needed
to slow down the progress. For notation convenience, we need the following definition.
Definition D.4. Let gA [t1 , t2 ] and gB [t1 , t2 ] be the number of good decodings of Alice and the
number of good decodings of Bob during times t1 , ..., t2 . Let bA [t1 , t2 ] and bB [t1 , t2 ] be the number
of bad decodings of Alice and the number of bad decodings of Bob during times t1 , ..., t2 .
Lemma D.5. For i = 0, ..., T − 1, let li+1 be the length of the binary description of the (i + 1)th edge on P during the first transmission where this edge is fully communicated. During time
m(i) + 1, ..., m(i + 1), the following is true.

22

1. If i is odd, then
gB [m(i) + 1, m(i + 1)] ≤ li+1 + ε · bB [m(i) + 1, m(i + 1)], and
gA [m(i) + 1, m(i + 1)] ≤ li+1 + (1 + ε) · bB [m(i) + 1, m(i + 1)].
2. If i is even, then
gA [m(i) + 1, m(i + 1)] ≤ li+1 + ε · bA [m(i) + 1, m(i + 1)], and
gB [m(i) + 1, m(i + 1)] ≤ li+1 + (1 + ε) · bA [m(i) + 1, m(i + 1)].
Proof. We will only prove the lemma for odd i’s; the case for even i’s follow for the same reason.
First, for any time period t1 , ..., t2 , it holds that gA [t1 , t2 ] ≤ gB [t1 , t2 ] + bB [t1 , t2 ]. This follows since
every good decoding of Alice stems from a symbol that was actually sent by Bob (rather than
inserted by Eve), which implies a decoding at Bob’s side (either bad or good).
Since we assume i is odd, ,at time m(i), Alice finishes sending the i-th edge on path P . From
the above claim we have gA [m(i) + 1, m(i + 1)] ≤ gB [m(i) + 1, m(i + 1)] + bB [m(i) + 1, m(i + 1)].
Then to prove Lemma D.5, it suffices to show that gB [m(i) + 1, m(i + 1)] ≤ li+1 + ε · bB [m(i) +
1, m(i + 1)] because the upper bound on gB [m(i) + 1, m(i + 1)] will directly give us the upper bound
on gA [m(i) + 1, m(i + 1)].
Let’s divide time period m(i) + 1, ..., m(i + 1) into three different types of time periods and
bound the number of good decodings of Bob. Let ei+1 be the (i + 1)-th edge of P .
1. Intervals [t1 , t2 ] in which ei+1 is not in Bob’s EdgeTable. In this interval gB [t1 , t2 ] = 0 because
if Bob has a good decoding, he adds the (i + 1)-th edge of P into his EdgesTable.
2. Intervals [t1 , t2 ] where ei+1 was inserted into the Bob’s EdgeTable at t1 , but removed at t2
before Bob has finished to fully send its encoding. In this time period, the “Live Points” of
ei+1 is increased for at least gB [t1 , t2 ] times, and each time it is increased by 1ε . At the same
time the “Live Points” of ei+1 decreases by 1 for at most bB [t1 , t2 ] times, until they reach 0
at time t2 . We thus have gB [t1 , t2 ] ≤ ε · bB [t1 , t2 ].
3. Interval [t1 , t2 ] where ei+1 was inserted into the Bob’s EdgeTable at t1 , and finally this edge’s
sending procedure is finished at time t2 . It is clear that t2 = m(i + 1), and gB [t1 , t2 ] ≤ li+1
since assuming ei+1 wasn’t removed from the table, after li+1 times of sending all the pages
in the table, Bob will have finished sending the encoding of ei+1 . Recall that a good decoding
implies Bob completed sending the last page in his table.
To sum up, we know that in case 1 and 2, we have gB [t1 , t2 ] ≤ ε · bB [t1 , t2 ]. And case 3 will happen
at most once. Therefore we have gB [m(i) + 1, m(i + 1)] ≤ li+1 + ε · bB [m(i) + 1, m(i + 1)] which
completes the proof.
In the following lemma, we bound the sum of the length of encodings of P ’s edges, regardless
of the progress of the protocol.
Lemma D.6. Given any instance of π ′ , that succeeds to fully communicate the first T ′ ≤ T edged
in P , for i = 1, ..., T ′ let li be the length of the binary encoding of i-th edge on P as communicated
in that instance. For i > T ′ , define li = 0. Then,
T
X
i=1

li ≤ T



log



NA + NB
T

23




+4

Proof. For any edge li let (δi , si ) be the encoding that was used in that instance of π ′ . By definition,
δi is the difference between the round ni where we start sending the encoding of li and round ni−2 ,
where the first bit of li−2 was communicated. Clearly, for any i > 2 we have li ≤ log(ni − ni−2 ) + 4,
while for the first two edges i = 1, 2 we have li ≤ log(ni − 0) + 4.
Then we have
X
X
(ni − ni−2 ) ≤ NA and n2 +
(ni − ni−2 ) ≤ NB ,
n1 +
4≤i≤T ′ ,
i even

3≤i≤T ′ ,
i odd

and by the concavity of logarithm, we have




T′


X
X
1
NA + NB
1


li ≤ log
n1 + n2 +
(ni − ni−2 )
+ 4.
+ 4 ≤ log
T′
T′
T′
i=1

3≤i≤T

Finally, note that x log(N/x) is monotonic increasing in x ∈ (0, N/e), thus the claim holds for
any T as long as T ′ ≤ T ≤ 2N/e.
With the above lemmas we can complete the proof of the main theorem.
Theorem D.7 (Restate of Theorem 5.1). For any ε > 0, the simulation π ′ of Protocol 2 with
N = ⌈ εT2 ⌉, and a (1 − ε)-edit distance tree code, solves P JP (T ) and is resilient to a (1/18 − ε)fraction of edit corruptions.
Proof. For notation convenience, let gA = gA [1, NA +NB ], gB = gB [1, NA +NB ], bA = bA [1, NA +NB ]
and bB = bB [1, NA + NB ]. Also let ρ = 1/18 − ε and α = 1 − ε. The proof is quite similar to the
one of Theorem 4.4 with some small difference in the parameters, specifically, we show that both
Alice and Bob have a large number of good decodings (compared to their bad decodings) which
implies they both output the correct value.
Claim D.8.

T
X
li ) ≥ (NA − (1 − 2ρ)N ) − (1 + ε)(bA + bB ).
gA − (
i=1

Proof. Recall that both NA and NB are in the range [N (1 − 2ρ), N ] because there are at most 2ρN
insertion/deletion errors. By Lemma D.3, we have
bA + bB
≤ NA − gA + NB − gB
≤ εNA + α2 (sc(τ1 ) + sc(τ2 )) + sc(τ1 ) − sc(τ2 ) + εNB + α2 (sc(τ3 ) + sc(τ4 )) + sc(τ3 ) − sc(τ4 )
8ρN
≤
+ 2εN
α

24

Using Lemma D.6 to bound

P

i li ,

and using the fact that ρ + ε ≤

1
18 ,

and that N ≥ T /ε2 , we have

T
X
li ) − (NA − (1 − 2ρ)N )
gA − (1 + ε)(bA + bB ) − (
i=1

NA + NB
) + 4) − (NA − (1 − 2ρ)N )
T
NA + NB
≥ NA − (2 + ε)(bA + bB ) − T (log(
) + 4) − (NA − (1 − 2ρ)N )
T
2N
8ρN
+ 2εN ) − T (log(
) + 4)
≥ (1 − 2ρ)N − (2 + ε)(
α
T
2N
) + 4)
≥ 11εN − T (log(
T
11
2
≥ T ( − 4 − log( 2 ))
ε
ε
>0
≥ NA − bA − (1 + ε)(bA + bB ) − T (log(

P
Similarly, we have gB − (1 + ε)(bA + bB ) − ( Ti=1 li ) − (NB − (1 − 2ρ)N ) > 0.
With the above claim and Lemma D.5, it follows that both Alice and Bob will finish sending
all the edges on P . Also by Lemma D.5, we have
T
X
li ).
gA [1, m(T )] ≤ ε · bA [1, m(T )] + (1 + ε)bB [1, m(T )] + (
i=1

Therefore, we have
gA [m(T ) + 1, NA + NB ] = gA − gA [1, m(T )] > bA + (NA − (1 − 2ρ)N ).
As Alice could have at most (NA − (1 − 2ρ)N ) good decodings after she gives her output, the
number of good decodings in the period between m(T ) and the point where Alice gives an output,
is larger than bA , suggesting the correct leaf will get at least that many votes. On the other hand,
any bad leaf will get at most bA votes, thus Alice outputs the correct leaf. A similar reasoning
applies for Bob.

E

Potent edit-distance tree code

In this section we show that it is simple to construct a relaxed notion of EDTC which is very
useful for most applications, namely potent edit-distance tree codes (PEDTC). This follows by
extending the techniques of Gelles, Moitra and Sahai for constructing a relaxed notion of standard
tree codes [14], to the edit-distance case.
Definition E.1. (Bad Interval) For a given d-ary prefix code of depth n let (A,B,D,E) be an αbad lambda (Definition 3.2). Let h be the depth of A and ℓ = max(|AD|, |AE|). We say that the
interval [h, h + ℓ] is α-bad.

25

Definition E.2 ((δ, α)-PEDTC). An (δ, α)-bad tree is a prefix code of depth n that has a path Q
for which the union of all bad intervals along Q (i.e., all bad intervals for which either the point E
or D of the bad-alpha inducing that bad interval is a node on Q) has a total length of at least δn.
If the tree is not an (δ, α)-bad tree, then we will call it a (δ, α)-potent edit-distance tree-code,
or (δ, α)-PEDTC for short.
In other words, in a PEDTC, for any given root-to-leaf path Q in the tree, if we sum up all the
nodes that belong to some bad lambda, their number would be less than δn. Next we show that a
tree whose labels are randomly chosen is a PEDTC with high probability.
Proposition E.3. For any constants δ, α ∈ (0, 1) and for any d ≥ 2, and for any |Σout | ≥
8

(32d3 ) (1−α)δ , a d-ary tree whose labels are independently and uniformly selected from Σout is a
(δ, α)-PEDTC with probability ≥ 1 − 2−n .
Proof. Assume we construct a tree by randomly picking each label uniformly from Σout . Assume
the obtained tree code is not (δ, α)-potent. Then, it means there exist a path Q and a set of nodes
{x1 , . . . , xd } along it, so that for each xi there exists points λxi = (A, B, D, E)xS
i where xi = E or
xi = D such that λxi is a α-bad lambda that induces the interval li , and that | i li | ≥ δn.
The following technical lemma says that there exists a subset of {x1 , . . . , xk } whose nodes induce
bad intervals of length at least δn/2 and the intervals are disjoint. Also, note that there are at
most 2n × 2n = 4n ways to distribute these disjoint intervals along the path Q. This is because, in
order to figure out the configuration of all intervals, we only have to determine which nodes are in
some interval and which nodes are ends of some interval.
Lemma E.4 ([28]). Let ℓ1 , ℓ2 , . . . , ℓk be intervals on N, and their union has length X. Then there
exists a set of indices I ⊆ {1, 2, . . . , k} such that the intervals indexed P
by I are disjoint, and their
total length is at least X/2. That is, for any i, j ∈ I, |ℓi ∩ ℓj | = 0, and i∈I |ℓi | ≥ X/2.

A proof is given in [28].
Now let’s first consider the probability that some interval li is bad when the path Q is given.
Let’s first see which lambda (A, B, D, E) can make the interval bad. We count these lambdas
by figuring out points A, B, D, E one by one. As Q and li are given, the point A is fixed. Next
let’s figure out the positions of D and E. We know that one of D and E should be on Q and
max(|AE|, |AD|) = |li |. It follows that there are at most 2|li | · d|li |+1 ways to pick E and D: there
are ≤ |li | ways to pick the point which lies on Q, and ≤ d|li |+1 ways to pick the point which is not
on Q; another factor of 2 is for choosing whether D or E is the one that lies on Q. Also note that
each such choice determines the position of B along Q. So in total, there are at most 2|li | · d|li |+1
lambdas that could induce the bad interval li on Q.
Given any lambda λxi Lemma 2.7 bounds that the probability that λxi is α-bad by
|Σout |−

(1−α) max(|AD|,|BE|)
2

≤ |Σout |−

(1−α)|li |
4

.
(1−α)|li |

So the probability that li on Q is α-bad is at most 2|li |d|li |+1 · |Σout |− 4 .
Using Lemma E.4 above,
P there exists a set I so that {λxi }i∈I induce disjoint intervals with
a total length of at least i∈I |li | ≥ δn/2. Since the intervals are disjoint, their probabilities to
occur are independent, and the probability that a specific pattern of intervals happens is bounded

26

8

by their product. By setting |Σout | ≥ (32d3 ) (1−α)δ we can bound the probability that a PEDTC is
(δ, α)-bad by
Pr[ PEDTC is (δ, α)-bad ] ≤

X
Q

≤

X
Q

X

k
Y

P r[li is a bad interval]

X

k
Y

2|li |d|li |+1 · |Σout |−

i=1
l ,...,lk :
Pk 1
i=1 |li |≥δn/2

Pk

(1−α)|li |
4

i=1
l1 ,...,lk :
|li |≥δn/2

i=1

≤ dn · 4n · 2n · 2n · d2n · |Σout |−

(1−α)δn
8

≤ (16d3 )n · (32d3 )−n
= 2−n .
Similar to [14, 15] we can further derandomize the above construction, by making the random
choice of each label coming out of a small-biased sample space (e.g., [2]). This immediately leads
to an efficient (randomized) construction of PEDTC with succinct description that succeeds with
overwhelming probability. We omit the details and refer the reader to [14, 15].

F

A coding scheme with a constant alphabet size and PEDTC

In this section, we show that our scheme work the same when the edit-distance tree code is replaced
with a potent edit-distance tree. Specifically, we prove that Protocol 2 still solves the pointer
jumping problem given a PEDTC.
First, we show an analogue of Lemma 3.10 used for decoding the tree, to the case of potent
trees.
Lemma F.1. Let C: Σnin → Σnout be a (δ, α)-PEDTC, and let rm ∈ Σm
out (m can be different
α
n
n
from n). If there exist sm ∈ ∪i=1 C(Σin )[1..i] such that SD(sm, rm) ≤ 2 and the end node of sm
on the tree is not in any bad interval of any path Q that contains sm, then sm will be the unique
message ∈ ∪ni=1 C(Σnin )[1..i] such that SD(sm, rm) ≤ α2 .
Proof. We
prove this lemma by contradiction. Suppose there exist two messages sm, sm′ ∈
P
n
∪ni=1 C( in )[1..i] such that both SD(sm, rm) ≤ α2 and SD(sm′ , rm) ≤ α2 , and also the end node of
sm on the tree is not in any bad interval of any path Q that contains sm. By the same argument
in Lemma 3.10, we know there is an α-bad lambda in C. Let this α-bad lambda to be (A, B, D, E),
then either D or E would be the end point of sm. Therefore, the end point of sm would be inside
some bad interval of some path Q. Now we get a contradiction.
We can now prove the main theorem of this section, namely, the existence of a coding scheme
that assumes P EDT C.
Theorem F.2. For any ε > 0, the simulation π ′ of Protocol 2 with N = ⌈ εT2 ⌉, and an (ε, 1 − ε)PEDTC instead of an edit distance tree code, solves P JP (T ) and is resilient to a (1/18−ε)-fraction
of edit corruptions.

27

Proof. The proof is very similar to the proof of Theorem 5.1. We are going to use exactly the same
notations like Definition D.2 and Definition D.4. And it is easy to check that Lemma D.1, Lemma
D.5 and Lemma D.6 still hold for Protocol 2 with PEDTC. The only difference is that we need to
make a slight change in Lemma D.3. We prove the following lemma as the analogy of Lemma D.3.
Lemma F.3. Alice has at least NA (1 − ε) + (1 − α2 )sc(τ2 ) − (1 + α2 )sc(τ1 ) − εNB good decodings.
Bob has at least NB (1 − ε) + (1 − α2 )sc(τ4 ) − (1 + α2 )sc(τ3 ) − εNA good decodings.
Proof. We prove the lemma for Alice; the lemma for Bob holds for the same reason. Compare
this lemma with Lemma D.3, it suffices to show that the number of new bad decodings of Alice
caused by changing edit distance tree code to PEDTC is at most εNB . For an instance of running
Protocol 2 with PEDTC, let Q be the path of sB [1..NB ](all the symbols sent by Bob) on the tree of
PEDTC C. By comparing Lemma 3.10 and Lemma F.1 we know that the corresponding sending
message of each new bad decoding has end point in some bad interval of Q. We also know that
each new bad decoding satisfies the constraint that the symbol just received in this decoding was
not inserted by the adversary. So the corresponding sending messages of new bad decodings have
different end points on the tree of PEDTC. By the definition of (ε, 1 − ε)-PEDTC, we know that
there are at most εNB nodes on Q which are in bad intervals. Therefore, the number of new bad
decodings is at most εNB .
Next we are going to prove an analogue of Claim D.8 for Protocol 2 with PEDTC.
Claim F.4.

T
X
li ) ≥ (NA − (1 − 2ρ)N ) − (1 + ε)(bA + bB )
gA − (
i=1

Proof. By Lemma F.3, we have
bA + bB
≤ NA − gA + NB − gB
≤ 2εNA + α2 (sc(τ1 ) + sc(τ2 )) + sc(τ1 ) − sc(τ2 )+
2εNB + α2 (sc(τ3 ) + sc(τ4 )) + sc(τ3 ) − sc(τ4 )
8ρN
+ 4εN
≤
α
P
1
, and that N ≥ T /ε2 , we have
Using Lemma D.6 to bound i li , and using the fact that ρ + ε ≤ 18
T
X
li ) − (NA − (1 − 2ρ)N )
gA − (1 + ε)(bA + bB ) − (
i=1

NA + NB
) + 4) − (NA − (1 − 2ρ)N )
T
NA + NB
≥ NA − (2 + ε)(bA + bB ) − T (log(
) + 4) − (NA − (1 − 2ρ)N )
T
2N
8ρN
+ 4εN ) − T (log(
) + 4)
≥ (1 − 2ρ)N − (2 + ε)(
α
T
2N
) + 4)
≥ 6εN − T (log(
T
≥ NA − bA − (1 + ε)(bA + bB ) − T (log(

28

6
2
≥ T ( − 4 − log( 2 ))
ε
ε
>0

After proving Claim F.4, in order to finish the proof, we just need to exactly follow the argument
after Claim D.8 in Theorem 5.1.

G

Upper bound on the noise fraction

In this section we show that no protocol can tolerate edit-corruption noise fraction of ρ = 1/6
or more, assuming that the parties are required to be correct after receiving (1 − 2ρ)N symbols.
Intuitively, since the effective protocol is shorter, the noise bound of 1/4 (that stems from the
ability to perform substitutions) becomes higher. Indeed, 1/4 · (1 − 2ρ)N corruptions out of a total
communication of 2N amounts to a fraction of errors of
ρ=

1/4 · (1 − 2ρ)N
2N

=⇒

1
ρ= .
6

We remind that the requirement to give an output comes from Eve’s possibility to delete 2ρN
at one party, making this party receive at most (1 − 2ρ)N symbols throughout the protocol. Below
we give a formal attack that demonstrate the bound of 1/6, under this stringent requirement.
Theorem G.1. Let π be an interactive protocol for P JP (T ) that is resilient to a ρ-fraction of edit
corruptions, and assume |π| = N . If both parties are required to output the correct output at round
(1 − 2ρ)N , and assuming an adversarial edit-corruption rate of ρ = 1/6, then no protocol outputs
the correct output with probability > 1/2.
Proof. Assume the parties run an instance of π on inputs (x, y) = (0, 0). Eve performs the following
attack (wlog, attacking Alice): For the first N/3 symbols sent by Alice, Eve deletes those symbols
and inserts back to Alice symbols that simulate Bob on input y = 1. Then (at round N/3 and
beyond), Eve does nothing.
Recall that Alice must output the correct value after receiving (1 − 1/3)N = 2N/3 symbols.
However her view at this time is indistinguishable from an instance of π on inputs (x, y) = (0, 1)
in which Eve corrupts Alice rounds [N/3, 2N/3] by deleting the symbols Alice is sending in these
rounds, and inserting Bob’s symbols assuming y = 0, and assuming the N/3-th symbol sent by
Alice is the first received by Bob. This implies that Alice cannot determine Bob’s input at round2
2N/3 under this attack, which proves the claim.
If we don’t require the the parties to output the correct value already at round (1 − 2ρ)N , then
it is possible to show an upper bound of ρ = 1/4 on the fraction of noise, similar to the case of
interactive protocols over standard noisy channels [7].

2

We mention that it may be possible for Alice to output the correct answer by round N .

29

A
B
D

E

Figure 2: An illustration of lambda structure

A
i
B
C
Figure 3: An illustration of the new tree C ′ for defining the potential probability Pi (C)

30

