Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. Ideally, the resulting scheme $\pi$ should be positive rate, computationally efficient, and achieve optimal error resilience.

While interactive coding over large alphabets is well understood, the situation over the binary alphabet has remained evasive. At the present moment, the known schemes over the binary alphabet that achieve a higher error resilience than a trivial adaptation of large alphabet schemes are either still suboptimally error resilient [11], or optimally error resilient with exponential communication complexity [19]. In this work, we construct a scheme achieving optimality in all three parameters: our protocol is positive rate, computationally efficient, and resilient to the optimal $\frac16 - \epsilon$ adversarial errors.

Our protocol employs a new type of code that we call a layered code, which may be of independent interest. Like a tree code, a layered code allows the coder to encode a message in an online fashion, but is defined on a graph instead of a tree.

§ INTRODUCTION

Interactive coding is an interactive analogue of error correcting codes [28, 21] that was introduced in the  seminal work of Schulman [25, 26, 27] and has been an active area of study since. While error correcting codes address the problem of sending a message in a way that is resilient to error, interactive coding addresses the problem of converting an interactive protocol to an error resilient one.

Suppose two parties, Alice and Bob, each with a private input, engage in a protocol $\pi_0$ to jointly compute a function $f$ of their private inputs. Given such a protocol $\pi_0$, can we design a protocol computing $f$ that is:

*  positive rate, i.e. $|\pi| = O(|\pi_0|)$ where $|\pi|, |\pi_0|$ denote the communication complexity of $\pi, \pi_0$,

*  computationally efficient,

*  resilient to the maximal possible fraction of adversarial errors?

The protocol should have a fixed number of rounds and speaking order. This parallels the notion of an efficiently encodable/decodable error correcting code with maximal distance.

The first positive rate interactive coding scheme, presented by Schulman [27], was resilient to $\frac1{240}$[Whenever we say that a protocol has resilience $r \in [0, 1]$ in the introduction and overview, we mean that for any $\epsilon$, there exists an instantiation that achieves resilience $r - \epsilon$.] adversarial errors (bit flips) over the binary channel but is exponentially inefficient, thus satisfying <ref> but not <ref> or <ref>. Many works since then sought to improve upon this scheme in computational efficiency and/or error resilience.

When the encoding alphabet is large constant sized, Braverman and Rao [5] first studied the problem of optimal error resilience. They constructed a large alphabet protocol achieving $\frac14$ error resilience, which they also showed to be optimal. Unfortunately, their protocol did not achieve computational efficiency <ref>. Computationally efficient schemes were not known until the work of [3], who converted the $\frac14$-error resilient, inefficient protocol to an efficient one achieving only $\frac1{16}$ error resilience. Finally, the work of [14] attained the best of both worlds: they constructed a protocol that was simultaneously efficiently decodable and resilient to $\frac14$ error, thus satisfying all three criteria.

On the other hand, over the binary alphabet, optimal interactive coding has remained less well understood. By simply replacing every letter of a large alphabet with its binary encoding, the large alphabet protocols give rise to efficient, positive rate interactive coding schemes achieving an error resilience of $\frac18$. By contrast, the best known upper bound on error resilience is $\frac16$ [10]. There are two works improving the error resilience beyond $\frac18$. The first is [11]. Their protocol is resilient to $\frac5{39}$ error, and is positive rate but inefficient. The second is [19], which constructs a scheme achieving the optimal $\frac16$-error resilience. However, both the communication and computational complexity can be up to exponential in the length of $\pi_0$. It thus remained open whether there exists a scheme resilient to the maximal amount of error, while also being positive rate and efficient.

In this work, we construct precisely such a scheme. Our result, along with comparison to existing work, is given in Figure <ref>.

For any $\epsilon > 0$ and any interactive binary protocol $\pi_0$ computing a function $f(x,y)$ of Alice and Bob's private inputs $x, y$, there exists a non-adaptive interactive binary protocol $\pi$ computing $f(x,y)$ that is resilient to $\frac16 - \epsilon$ adversarial erasures. The communication complexity is $O_\epsilon(|\pi_0|)$ and the computational complexity is $\tilde{O}_\epsilon(|\pi_0|)$.

Protocol     Positive Rate?     Efficient?     Error Resilience

[14]     yes     yes     $1/8$

[11]     yes     no     $5/39$

[19]     no     no     $1/6$ (optimal)

This work     yes     yes     $1/6$ (optimal)

Interactive coding schemes over the binary channel

Layered Codes.

Our protocol crucially relies on a new type of code that we call a layered code, which generalizes a tree code. Recall that tree codes [26, 27] are error correcting codes that can be updated in an online manner: the $i$'th symbol in a codeword is dependent only on the first $i$ characters in the message. One can view a tree code as an assignment of code symbols $\Sigma_{code}$ to the edges of the infinite $|\Sigma_{mes}|$-ary rooted tree, where $\Sigma_{mes}$ is the alphabet of the message text. To encode a message $\in \Sigma_{mes}^*$, one simply follows the rooted path specified by the message and reads the code symbols off the edges.

Instead of being defined on trees, layered codes are an assignment of $\Sigma_{code}$ to a certain kind of graph called layered graphs. A layered graph is a directed graph where vertices are partitioned into layers such that there is only one vertex (the root node) in layer $0$, and each vertex in layer $i$ has out-edges labeled with $\Sigma_{mes}$ to vertices in layer $i+1$.[Note that tree codes are layered codes, so our notion of a layered code generalizes tree codes.] As with tree codes, to encode a message $\in \Sigma^*_{mes}$, one simply follows the rooted path specified by the message and reads the code symbols off the edges.

In the literature, tree codes with a variety of distance or decoding properties have been studied [27, 18, 1]. In our protocol, however, we will need our layered codes to satisfy a certain new special property we call sensitivity. Intuitively, sensitivity means that a corrupted layered code can be entirely decoded correctly as long as the latest symbol was received correctly. More precisely, we show that:

There exists a layered code (i.e. an assignment of labels to a layered graph) with the following property: for any string $w \in \Sigma_{code}^n$ and message text $x \in \Sigma_{mes}^n$, $w[1:i]$ uniquely decodes to $v(x[1:i])$ for almost every $i$ for which $w[i] = \PikC(x)[i]$. Here, $v(x[1:i])$ denotes the vertex at the end of the rooted path specified by $x[1:i]$.

Layered codes may be of independent interest, beyond the application to our protocol. One might also want to generalize more of the study of tree codes to the graph setting. We leave this as an open topic, and discuss this further in Section <ref>.

§.§ Related Work

Our work relates primarily to the fields of interactive coding and tree codes.
Besides the works we have already discussed, we mention the following related works.

§.§.§ Interactive Coding

Non-adaptive interactive coding (when the protocol is fixed length and fixed speaking order) was studied starting with the seminal works of Schulman [25, 26, 27] and continuing in a prolific sequence of followup works, including [5, 6, 3, 4, 20, 1, 9, 16, 15, 10, 14, 17, 11, 19].

We note that there are many other works studying variations upon this original interactive coding setup, including adaptive and multi-party schemes. We refer the reader to an excellent survey by Gelles [13] for an extensive list of related work.

Other binary schemes resilient to $\frac16$ error.
[10] studies interactive coding over the feedback channel. Over the feedback channel, Alice and Bob are given the extra power to know, instantly, what the other party received at the other end of the channel when they send a message. In this setting, [10] constructs a positive rate, efficient protocol resilient to $\frac16$ error, which is optimal in the feedback setting as well. By contrast, we achieve $\frac16$-error resilience with positive rate in the standard setting without feedback.

The protocol of [10] relies on feedback for a “guess” of the transcript so far, and then the party responds according to whether or not they agree with this guess. The protocol of [19] (achieving $\frac16$ error resilience in channels without feedback, but inefficiently) also uses this idea, however providing (unreliable) feedback through future messages instead. One step in our protocol uses this idea as well, following the blueprint of the construction in [19].

We also mention the work on obtaining interactive protocols that are efficient: protocols where Alice and Bob can compute their next message and output their final answer in polynomial time. While Braverman and Rao's protocol [5] is resilient to $\frac14$ corruption over a large alphabet and incurs only a constant blowup in communication complexity, the parties' computational efficiency incurs exponential blowup.

The work of [14] which draws inspiration from [3] addresses this problem. They provide an algorithm which takes a protocol and “boosts” it, lowering the computational complexity while increasing the alphabet size. We use a similar method to make our protocol computationally efficient while avoiding the alphabet blowup.

§.§.§ Tree codes.

Tree codes were first introduced by Schulman [26, 27] and have been studied since in a variety of works [18, 6, 23, 12, 2, 24, 8, 7].
Tree codes are a key ingredient in achieving constant rate interactive coding schemes. They also have important uses as streaming codes for both Hamming errors [12] and synchronization errors [2, 22]. Recently, there has been work towards finding explicit tree codes with a constant sized alphabet that are efficiently decodable and encodable [8, 7].

We specifically mention the concept of list tree codes introduced in [1], which are the list-decoding analogue of error correcting codes in the tree code setting. Our concept of sensitive layered codes generalize and strengthen Braverman and Efremenko's definition of list tree codes.

§ TECHNICAL OVERVIEW

We begin by recalling at a high level the binary protocol of [19], which achieves optimal error resilience $\frac16 - \epsilon$, but whose communication complexity is quadratic in the input lengths.

Suppose Alice and Bob have private inputs $x, y \in \{ 0, 1 \}^n$. Consider the task of message exchange, where the goal is for Bob to learn $x$ and for Alice to learn $y$. The protocol of [19] is a $(\frac16-\epsilon)$-error resilient protocol achieving message exchange, where the communication complexity is $O_\epsilon(n^2)$.

The protocol works as follows. Alice and Bob each keep a track of a guess $\hat{y}$ or $\hat{x}$ for the other party's input, initially set to $\emptyset$, and a weight $w_A$ or $w_B$ indicating their confidence for their guess $\hat{y}$ or $\hat{x}$ respectively, initially set to $0$.

The idea is that Alice can ask a question by sending Bob her guess $\hat{y}$ encoded in an error correcting code. Bob can then send her an answer telling her how to update $\hat{y}$ to bring it closer to his actual input $y$: append $0$ ($0$), append 1 ($1$), delete the last bit ($\rewind$), or “bingo – you got it right!” ($*$). (This last instruction $*$ tells Alice to increase $w_A$. If Alice receives an instruction to modify $\hat{y}$ while $w_A > 0$, she decreases $w_A$ by $1$ instead.) Since Bob's answer is always one of four options, his possible answers can be made to be relative distance $\frac23$ apart (e.g. $000, 011, 101, 110$), so that the adversary would have to corrupt $\ge \frac13$ of Bob's bits sent (or $\frac16$ overall) to prevent Alice from making good updates to $\hat{y}$ (i.e. updates that get $\hat{y}$ closer to $y$).

Now, since both Alice and Bob have to learn the other's input, Alice and Bob simultaneously ask a question and answer the other party's last question. In other words, Alice's message is always of the form $\ECC(\hat{y}, x^*, \delta)$, where $x^*$ is the question she just heard from Bob and $\delta$ is the instruction on how to update $x^*$ to bring it closer to $x$. Similarly, Bob's message is always of the form $\ECC(\hat{x}, y^*, \delta)$. Here, $\ECC$ is a code with certain distance properties, including that for any $x',y'$ the four codewords $\{ \ECC(x', y', 0), \ECC(x', y', 1), \ECC(x', y', \rewind), \ECC(x', y', *) \}$ should be pairwise relative distance $\frac23$ from each other.

However, there are two problems with this current algorithm:

*  The adversary can simultaneously corrupt both the question and answer in Bob's message $\ECC(\hat{x}, \hat{y}, \delta)$ by only corrupting $\frac12$ of the message, so that Alice receives an incorrect answer and thus makes a bad update for only $\frac12$ cost.

*  The adversary can partially corrupt Bob's message (so that the message Alice receives is not any codeword), so Alice does not know what question to answer.

The algorithm of [19] fixes these problems with two additional rules.

* When Alice receives a message $\ECC(x', \hat{y}, \delta')$, she usually only updates with probability $0.5$. However, if $x'=x$ (i.e. Bob has already figured out her input), she updates with probability $1$.

* When Alice receives a partially corrupted message where she cannot determine what question to answer, she defaults to sending $\ECC(\hat{y}, x, *)$. Correspondingly, when Bob receives any message $\ECC(y', x', *)$ where the update instruction is $*$, he updates $\hat{x}$ to be closer to $x'$.

Both these new rules require one important fact: that Alice knows what Bob's correct output ought to be (her input $x$).

For us, we will be simulating a noiseless protocol $\pi_0$ where the final transcript depends on both parties' private inputs, so that neither Alice nor Bob knows what the correct final transcript ought to be. This is the main barrier to making the protocol of [19] run in time $O_\epsilon(|\pi_0|^2)$ as opposed to in time $O_\epsilon(n^2)$.

§.§ Obtaining Communication Complexity $O_\epsilon(|\pi_0|^2)$

The first modification we will make is to create an interactive coding scheme that can simulate general protocols, instead of just message exchange, in quadratic time. By doing this, we will obtain a protocol with communication complexity $O_\epsilon(|\pi_0|^2)$ instead of $O_\epsilon(n^2)$.

At a high level, in our protocol, in each message Alice and Bob either asks a question or answers a received question, but not both.

This is as opposed to the protocol of [19], in which question asking and answering are always done simultaneously. We remark that this removes issue <ref> with the [19] protocol, since now answers no longer have a question component so that all possible answers $\{ \ECC(r^*, 0), \ECC(r^*, 1), \ECC(r^*, \rewind), \ECC(r^*, \bullet) \}$ to the same question $r^*$ are distance $\frac23$ apart.

More concretely, Alice and Bob each keep track of a guess for the complete noiseless transcript, denoted $T_A$ or $T_B$ respectively, along with a weight $w_A$ or $w_B$ signaling how confident they are that the current transcript guess is correct. We have that $w = 0$ unless the corresponding transcript guess $T$ is complete, meaning $|T| = |\pi_0|$. Alice's transcript guess $T_A$ always has odd length, i.e. she is the last to speak, unless $T_A$ is a complete transcript or is the empty transcript. Similarly, Bob's transcript guess $T_B$ always has even length. Let $\cT$ denote the noiseless transcript, so that the goal is for Alice and Bob to have $T_A = T_B = \cT$ by the end of the protocol. In what follows, we describe the protocol from Alice's point of view, but Bob's behavior is equivalent.

Every round, Alice sends a message of the form $\ECC(T, \delta \in \{ 0, 1, \rewind, ? \})$, where $\delta = ?$ signals that she is asking a question and $\delta \in \{ 0, 1, \rewind \}$ signals that she is answering a question. Specifically, when Alice asks a question, she sends $\ECC(T_A, ?)$. She answers a question $T^*_B$ by sending $\ECC(T^*_B, \delta)$, where $\delta \in \{ 0, 1, \rewind \}$ is

* $\rewind$ if $T^*_B$ is not consistent with her own behavior on input $x$.

* her next message $0$ or $1$ given the consistent transcript prefix $T^*_B$ (if $T^*_B$ is a complete transcript, then her next message is just $1$).

Here, $\ECC$ is a code satisfying that for any $T^*$ the four words $\ECC(T^*, 0)$, $\ECC(T^*, 1)$, $\ECC(T^*, \rewind)$, $\ECC(T^*, ?)$ have relative distance $\frac23$ and all other pairs of codewords are relative distance $\frac12$ apart. Such a code was shown to exist in [19].

Alice determines whether to ask or answer based on the message she just received:

* As long as she receives an answer (not necessarily to the question she previously asked), she asks a question.

* Whenever Alice receives a question, she answers it. There is an exception, which is when the question received is a complete transcript consistent with Alice's own input $x$. In this case, Alice asks her own question. This mechanism allows Alice and Bob to switch who is asking vs. answering once the asking party has made sufficient progress and now knows $\cT$.

Furthermore, every time Alice receives a message from Bob, she needs to update $(T_A, w_A)$ accordingly:

* When she receives an answer to her question $\ECC(T_A, \delta\in \{0,1\})$, she concatenates $\delta$ and her resulting next message to the end of $T_A$. (If $T_A$ is a complete transcript, she instead increments $w_A$.)

* If she receives $\ECC(T_A, \rewind)$, assuming $w_A = 0$ she deletes the last two messages (one of hers and one of Bob's) from $T_A$, and otherwise if $w_A > 0$ she simply decreases $w_A$ by $1$.

* If she receives a question $\ECC(T^*_B,?)$ from Bob, where $T^*_B$ corresponds to a complete transcript that is consistent with her input $x$, she updates $T_A$ to be one step closer to $T^*_B$ with $0.5$ probability.

There is an exception to this rule, which is when $T^*_B = T_A$. This can only happen if $T^*_B = T_A$ is either $\emptyset$ or a complete transcript, as in general $T_A$ is of odd length and $T_B$ is of even. In this case, with probability $1$ instead of $0.5$, Alice increases her weight $w_A$ on the transcript $T_A$ by $1$. This is because when $T_A = T_B = \cT$, we want both Alice and Bob to make more progress simultaneously.[The potential function we care about is $[\text{Alice's progress}] + \min\{ [\text{Bob's progress}], |\pi_0| \}$, so once Bob's progress is $\ge |\pi_0|$ signaling that $T_B = \cT$, we need Alice to be updating with probability $1$ each time she correctly receives Bob's message.] Similarly, Bob also needs to be updating with probability $1$ whenever he receives a question from Alice equal to $T_B$.

* Otherwise, she does not update $T_A$ or $w_A$.

So far, we have described the protocol when the parties receive full codewords. When messages are partially corrupted so that the received message is not a codeword, a party will default to asking a question with probability proportional to the distance from the nearest codeword, and otherwise employ the above behavior. This addresses issue <ref>. We remark that the default message being a question is the second idea that allows us to escape from needing for Alice and Bob to know what the other party's output ought to be, since instead of defaulting to sending the answer $(x, *)$ or $(y, *)$ one now defaults to asking a question.

§.§ Reducing the Communication Complexity to $O_\epsilon(|\pi_0|)$

Now that we have an optimally error resilient interactive coding scheme that can simulate protocols with $O_\epsilon(|\pi_0|^2)$ communication complexity, the next step is to reduce the communication complexity to $O_\epsilon(|\pi_0|)$.

Currently, the quadratic factor in the communication complexity arises because we need $O_\epsilon(|\pi_0|)$ rounds to simulate the protocol, and in each round the parties are sending either their transcript guess or the transcript guess they are answering, both of which takes $O_\epsilon(|\pi_0|)$ bits. If we could reduce the amount of communication needed to send a transcript guess to $O_\epsilon(1)$, then we could achieve our desired $O_\epsilon(|\pi_0|)$ total communication.

Consider first the task of a party sending their own transcript guess as a question such that each message is only $O_\epsilon(1)$ bits. The traditional solution for this problem in interactive coding is to use tree codes [26, 27], which are essentially error correcting codes that one can update in an online way. In our setting, since a new transcript guess is a two-bit modification of the last transcript guess, we can have Alice and Bob track a sequence of updates $U_A, U_B \in \{ 0, 1, \rewind, \bullet \}^*$ they have made to obtain their current transcript guess, where $\bullet$ is a placeholder update that simply means “do nothing.” Then, the question asker will send just the next two symbols of a tree code encoding of $U_A$ or $U_B$, which will take $O_\epsilon(1)$ bits per round. The receiver can then decode the entire history of received messages to determine the sequence of updates, which will allow them to determine the transcript being asked.

In our $O_\epsilon(|\pi_0|^2)$ protocol, we had the property that for Alice to successfully decode the asked transcript, she only needed to receive the last message (which contained the entire asked transcript) correctly. However, in a traditional tree code, even if Alice received the last message correctly, she cannot decode the message history if she received a high fraction (specifically more than half) of the previous messages incorrectly. In this paper, we present a new notion of sensitive tree codes that in fact satisfy a stronger property, that for all but $\epsilon |w|$ indices $i$ where $w[i] = LTC(x)[i]$, it in fact holds that decoding $w[1:i]$ will uniquely give $x[1:i]$. This essentially means that Alice only needs to receive the previous symbol of a sensitive tree code correctly to determine the entire message so far.[Sensitive tree codes can also be thought of as codes where the message can (usually) be decoded uniquely as long as the suffix distance to the original codeword is at most $1-\epsilon$. Previous results only guaranteed a message could be decoded correctly when the suffix distance was $\frac12-\epsilon$ to the original codeword; for example Lemma 2.3 in [13].]

Our notion of sensitive tree codes follows a similar construction as list tree codes, introduced by Braverman and Efremenko [1]. These are codes which guarantee that there is on average some constant number of ways to decode a random prefix of a string $w$. What we show is that this constant can actually be made $1$.

Still, we need answers to have message size $O_\epsilon(1)$ as well. To achieve this, we make the following modification to the answer format. Instead of sending $\ECC(T^*, \delta)$, which has size $O_\epsilon(|\pi_0|)$, a party who wishes to answer the transcript specified by the sequence of operations $U^*$ instead sends $\ECC(\sigma, \delta)$, where $\sigma$ is the last two symbols in the list tree code encoding of $(U^* || \bullet\bullet)$.

There is still one case where the new protocol is not analogous to the one from Section <ref>. In the protocol from Section <ref>, when Alice is asking the same transcript $T'$ that she is answering, she sends $\ECC(T',?)$ as a question. Bob will notice that $T'$ happens to be the same as the question he asked, and update with probability $1$. In some sense, this message gives Alice the benefits of both asking and answering a question. However, in the new setup, in order to ask a question, Alice has to send the last two symbols of the encoding of $U_A$, but in order to answer $U^*_B$ she has to send the last two symbols of $U^*_B$. The issue is that these symbols may not be the same, even if $U_A$ and $U^*_B$ correspond to the same complete transcript $T'$.

This leads us to define a new sort of online-updatable code, where if two histories correspond to the same transcript, even if the histories themselves are different, the next tree code encoding of a given edge is the same. This requires defining a code on a particular graph rather than on trees.

§.§ Codes on Graphs

Consider the rooted $|\Sigma_{in}|$-ary tree T. A sequence of symbols $\in \Sigma_{in}$ can be associated with a rooted path of T in the natural way. A sensitive tree code is then an assignment of symbols in $\Sigma_{out}$ to the edges of T. To encode a string $x \in \Sigma_{in}^k$, one simply traverses the corresponding rooted path and writes down the symbols seen. This gives an encoding $\in \Sigma_{out}^k$.

The problem with using sensitive tree codes for our purposes is that Alice may have followed one path to get to the correct transcript $T_A = \cT$ while Bob followed another to get to $T_B = \cT$. Then, the next edge for Alice is different then the next edge for Bob, which means that one cannot hope to coincide sending the next symbol of one's own tree code with answering the other's.

Our key observation is that the encoding of the next symbol depends only on the transcript so far, not the full history of symbols.

So, we can actually coincide all nodes of T that lead to the same transcript. We define the following graph.

The Graph.

The graph $G$ that we will be interested in is defined as follows:

* $G$ is a directed graph with vertices partitioned into layers $1,2,\ldots$. In the $i$'th layer, there is a vertex for each possible transcripts of length $\le i$. In particular, there is one vertex in the $0$'th layer, namely, the empty string.

* We set $\Sigma_{in} = \{ 0, 1, \rewind, \bullet \}$ to be the possible update instructions, where $\bullet$ means simply “do nothing.” Each vertex in the $i$'th layer has $4$ children in the $(i+1)$'th layer, corresponding to the $4$ resulting transcripts obtained by applying an instruction in $\Sigma_{in}$ to the vertex's associated transcript.

Note that any sequence of updates $\in (\Sigma_{in})^*$ corresponds to a rooted path in $G$. Furthermore, any two equal length sequences of updates that result in the same transcript end at the same node.

The Code on $G$.
We define a layered code to be an assignment of elements of $\Sigma_{out}$ to the edges of $G$. Then, to encode $x \in (\Sigma_{in})^*$, one simply follows the path specified by $x$ and records the $|x|$ symbols seen on the edges.

We will use a specific layered code $\PikC$ that exhibits the same behavior as the sensitive tree codes we defined in Section <ref>. We call these codes sensitive layered codes. In particular, the property we want is that for all but $\epsilon |w|$ indices $i$ where $w[i] = \PikC(x)[i]$, decoding $w[1:i]$ gives a unique vertex (i.e. transcript guess) equal to the vertex at the end of the rooted path specified by $x[1:i]$.

We will not go into depth how such to prove the existence of such a code here, but instead refer the reader to Section <ref> for a comprehensive discussion. While much of our construction and proofs are motivated by the list tree codes of [1], we remark that there are several subtleties that need to be carefully addressed.

§.§ Boosting to Achieve Computational Efficiency

Thus far, we have described how to obtain an interactive coding scheme that is resilient to $\frac16 - \epsilon$ error and has communication complexity linear in the size of the original protocol. Unfortunately, since decoding our sensitive layered code is inefficient (in fact, takes exponential time), this means that the computation needed by both parties is exponential in $|\pi_0|$. Thus, the final needed component is a way to make our scheme efficiently computable.

Over a large alphabet, an efficiently computable, positive rate scheme that is maximally error resilient was constructed by [14]. They obtained this efficient scheme in two steps: first by boosting a known inefficient, exponential-time scheme [5] to obtain an efficient protocol with a list-decoding guarantee, and second by applying a transformation that takes a list-decoding protocol to a unique-decoding protocol. We remark that this second transformation crucially relies on using a large alphabet and thus will not be permittable for us.

The boosted list-protocol is obtained as follows. First, they split up their original noiseless protocol into $\log^4 |\pi_0|$ size chunks. Then, they use their inefficient scheme to simulate the following noiseless subprotocol $O_\epsilon(\frac{|\pi_0|}{\log^4 |\pi_0|})$ times:

* Alice and Bob first find the longest transcript they have both simulated so far. This takes $O(\log^4 |\pi_0|)$ rounds.

* Next, they run the next chunk of $\log^4 |\pi_0|$ rounds of the noiseless protocol.

Whenever a simulated subprotocol results in a completed transcript, that complete transcript obtains a vote. At the end, they show that as long as there was not too much corruption, the correct transcript must be one of the transcripts with the most votes (i.e. each party obtains a list of possible transcripts containing the correct one). Note that this results in a protocol with computational complexity $O_\epsilon(\frac{|\pi_0|}{\log^4 |\pi_0|}) \cdot \exp (\log^4 |\pi_0|) = \exp(\polylog |\pi_0|)$ time, which is considerably better than $\exp(|\pi_0|)$. Recursively boosting a second time gets the computational complexity down to $\poly(|\pi_0|)$. A third time reduces the computational complexity to $\tilde{O}_\epsilon(|\pi_0|)$.

[14]'s second step is to apply a transformation that takes a list-decoding protocol to a unique decoding protocol, incurring a blowup in the alphabet size. Since we are working over a binary alphabet, we cannot afford to apply this same second transformation. Instead, we notice that our inefficient protocol has a property that we call scaling. Essentially, this means that the amount of confidence Alice and Bob have in their final transcript guesses is directly related to the amount of corruption the adversary put in. More specifically, if the adversary corrupted $\frac16 - \rho$ of the communication ($\rho > 0$), then Alice and Bob end up with the correct transcript and are $\propto \rho$ confident in its correctness; and if the adversary corrupted $\frac16 + \rho$ of the communication, then Alice and Bob may end up with incorrect transcripts but they are only $\propto \rho$ confident. We can understand this as saying that $\frac16 - \rho$ corruption results in a net good confidence of $\rho$ (where $\rho$ can be positive or negative: $\rho < 0$ means that there was $\rho$ confidence in a bad transcript).

This allows us to consider the same boosting transformation that [14] did, with the following caveat: whenever a simulated subprotocol results in a complete transcript, that transcript obtains a vote proportional to the confidence the parties have in the simulated protocol's correctness. Then, if the adversary corrupts $< \frac16$ of the protocol, the net good votes (i.e. the number of votes for the correct transcript minus the total number for all incorrect transcripts) must be positive, so Alice and Bob can determine the correct transcript.

We elaborate more on our boosting transformation in Section <ref>.

§ PRELIMINARIES

Notation. In this work, we use the following notations.

* The function $\Delta(x, y)$ represents the Hamming distance between $x$ and $y$.

* $x[i]$ denotes the $i$'th bit of a string $x \in \{ 0, 1 \}^*$.

* $x[i:j]$ denotes the $i\ldots j$'th bits of $x \in \{0,1\}^*$.

* $x||y$ denotes the string $x$ concatenated with the string $y$.

§.§ Noise Resilient Interactive Communication

We formally define a non-adaptive interactive protocol and with error resilience. Our definition is for the binary alphabet $\{ 0, 1 \}$.

A two-party non-adaptive interactive coding scheme $\pi$ for a function $f(x, y) : \{ 0, 1 \}^n \times \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^o$ is an interactive protocol consisting of a fixed number of transmissions, denoted $|\pi|$. In each transmission, a single party fixed beforehand sends a single bit to the other party. At the end of the protocol, each party outputs a guess $\in \{ 0, 1 \}^o$.

We say that $\pi$ is resilient to $\alpha$ fraction of adversarial errors with probability $p$ if the following holds. For all $x,y \in \{ 0, 1 \}^n$, and for all adversarial attacks consisting of at most $\alpha \cdot |\pi|$ errors, with probability $\ge p$ Alice and Bob both output $f(x,y)$ at the end of the protocol.

It is known that over a binary alphabet, one cannot achieve an error resilience greater than $\frac16$.

There exists a function $f(x, y)$ of Alice and Bob's inputs $x,y\in\{0,1\}^n$, such that any non-adaptive interactive protocol over the binary bit flip channel that computes $f(x, y)$ succeeds with probability at most $\frac12$ if a $\frac16$ fraction of the transmissions are corrupted.

§ BOOSTING: OBTAINING COMPUTATIONAL EFFICIENCY

In this section, we show how to boost the computational efficiency of a scheme. Our boosted protocol draws inspiration from the list-decoding boosting scheme of [14], which drew ideas from [3]. We begin by recalling the necessary setup from [14].

§.§ The Simulation Paradigm of [14, 3]

Assume that $\pi_0$ is an alternating binary protocol of length $n_0$ (any binary protocol can be made alternating by increasing the communication by at most a factor of $2$). We can view $\pi_0$ as a protocol tree $\mathbb{T}$, in which the edges at odd levels correspond to Alice's messages and the edges at even levels correspond to Bob's messages. For any input $x$, $\pi_0$ defines a subset $S_A$ of edges at the odd levels corresponding to Alice's possible responses, and similarly, for any input $y$, $\pi_0$ defines a subset $S_B$ of edges at the even levels corresponding to Bob's possible messages. Note that for any $(x, y)$, $S_A \cup S_B$ defines a unique rooted path $\cT$ corresponding to the noiseless protocol $\pi_0(x,y)$. The goal is for both Alice and Bob to determine $\cT$.

To do this, Alice and Bob each keep track of a set of edges $\cE_A$ and $\cE_B$. Initially both sets are empty. In each of many iterations, Alice (resp. Bob) will add some edges to $\cE_A$ (resp. $\cE_B$) extending some existing path in $\cE_A$ (resp. $\cE_B$). We remark that any new edges Alice adds must be consistent with her own behavior on her input $x$, i.e. she never adds an edge in an odd layer that does not belong to $S_A$. The same holds for Bob. It thus holds that at any point the unique longest rooted path in both $\cE_A$ and $\cE_B$ is a prefix of $\cT$.

The process by which Alice and Bob add edges to their respective set in each iteration is as follows. They first run a subprotocol to determine their longest common rooted path. Then, they run the next $\log^4 n_0$ rounds of the noiseless protocol. They perform both these steps under a single error-resilient simulation. The idea is that every time not too many errors have happened in an iteration, both Alice and Bob add $\log^4 n_0$ edges to the correct path corresponding to $\cT$.

If the longest common rooted path is a path from the root to a leaf, then Alice and Bob instead add some weight to that leaf. Over the course of many iterations, the hope is that the leaf with the largest weight at the end of the protocol should correspond to $\cT$. We remark that [14] showed a list-guarantee assuming not too many errors occurred: at the end of this procedure, Alice and Bob will each have a small list of leaves each containing the true leaf corresponding to $\cT$. (They then need to run this procedure many times in parallel with sending an error correcting code in order for both parties to narrow down the correct transcript, resulting in an alphabet blowup.) For us, we will show that if our inefficient simulation has a property known as scaling (see Definition <ref>), then at the end of this procedure Alice and Bob will each have narrowed down to a unique leaf, precisely, the leaf corresponding to $\cT$, provided not too many errors occurred.

The Tree-Intersection Problem.
The problem of finding their longest shared path is called the tree-intersection problem. Precisely, assuming Alice and Bob have sets of edges $\cE_A$ and $\cE_B$ respectively each forming a rooted tree under the promise that $\cE_A \cap \cE_B$ is a rooted path, the problem is for Alice and Bob to recover this rooted path using as little communication and computation as possible.

In [14], they give a data structure for $\cE_A$ and $\cE_B$ that optimizes the computational complexity of a protocol solving the tree-intersection problem.

There is an incremental data structure that maintains a rooted subtree of the rooted infinite binary tree under edge additions with amortized computational complexity of $\tilde{O}(1)$ time per edge addition. Furthermore, for any $c = \Omega(1)$ and given two trees of maximum size $n$ maintained by such a data structure, there is a tree-intersection protocol that uses $100 c \log^4 n$ rounds of communication over a noiseless binary channel, $O(c \log^4 n)$ bits of randomness, and $\tilde{O}(1)$ computation steps to solve the tree intersection problem, that is, find the intersection path with failure probability at most $2^{-c \log^4 n}$.

§.§ Scaling Schemes

We now define precisely what we mean by a scaling scheme. Intuitively, a scaling scheme is a scheme in which Alice and Bob output a confidence in addition to a transcript. This confidence should give a bound on the total error in the protocol. For instance, if there is no corruption, then Alice and Bob should output the correct transcript with large confidence. If there is some corruption, then Alice and Bob should output the correct transcript with smaller confidence. If there is too much corruption, then Alice and Bob may output an incorrect transcript, but their confidence cannot exceed a certain quantity specified by the amount of error that occurred (i.e. if the adversary wishes Alice and Bob to be more confident in an incorrect transcript, she must corrupt more of the protocol).

A scheme for simulating a noiseless protocol of length $n$ is $(\rho, \epsilon, \mu_\epsilon)$-scaling if, at the end of the protocol, Alice and Bob output guesses $T_A$ and $T_B$ for the noiseless transcript $\cT$ along with confidences $c_A, c_B \in [0, 1]$, with the following guarantees:

* Consistency:
All of Alice's messages in $T_A$ are consistent with her behavior in $\pi_0$ on input $x$. Similarly, all of Bob's messages in $T_B$ are consistent with his behavior in $\pi_0$ on input $y$.

* Scaling 1:
If a $\delta < (1-\epsilon) \cdot \rho$ fraction of the scheme was corrupted, then

\[
\Pr \left[ T_A = T_B = \cT ~\wedge~ c_A, c_B \ge 1 - \frac{\delta}{\rho} - \epsilon \right] \ge 1 - \mu_\epsilon(n).
\]

* Scaling 2:
If $\delta \ge (1 - \epsilon) \cdot \rho$ fraction of the scheme was corrupted, then

\[
\Pr \left[ \left( T_A \not= \cT ~\wedge~ c_A > \frac{\delta}{\rho} - 1 + \epsilon \right) \vee \left( T_B \not= \cT ~\wedge~ c_B > \frac{\delta}{\rho} - 1 + \epsilon \right) \right] \le \mu_\epsilon(n).
\]

§.§ Boosting

Let $\cP'$ be a $(\rho, \epsilon, \mu_\epsilon)$-scaling scheme that simulates noiseless protocols of length $n'$ by a protocol of length $r_\epsilon(n')$ that has computational complexity $T_\epsilon(n')$. Choose $C_\epsilon \ge 100/\epsilon + 1$.

For a protocol $\pi_0$ that has length $n_0$, and on inputs $(x, y)$, Alice and Bob run the following scheme:

* Alice and Bob each keep track of a list $\cE_A, \cE_B \subseteq \mathbb{T}$ of edges they have simulated so far, using the data structure from <ref>. Initially, $\cE_A, \cE_B = \emptyset$. They also each keep track of a dictionary[Roughly, a dictionary is implemented by a hash table.] $\cL_A, \cL_B$ of leaves, i.e. full transcripts $T$ of $\mathbb{T}$, mapping to $\bbR_{\ge 0}$. Initially, for any full transcript $T$ of $\mathbb{T}$, $\cL_A[T] = \cL_B[T] = 0$.

* For $i = 1, \dots, \frac{n_0}{\epsilon \log^4 n_0} =: \beta$, they use $\cP'$ to simulate the following $n' = C_\epsilon \cdot \log^4 n_0$ round noiseless protocol:

* Alice and Bob run the tree-intersection protocol given in Theorem <ref>, using $(C_\epsilon - 1) \log^4 n_0$ rounds and $\tilde{O}(1)$ computation steps. At the end, with probability $1 - 2^{-((C_\epsilon - 1)/100) \cdot \log^4 n_0} \ge 1 - 2^{-\log^4 n_0/\epsilon}$, the two parties have determined the common rooted path $p = \cE_A \cap \cE_B$.

* After Alice and Bob have determined a common path $p$, they fix $p$ to be the transcript prefix of $\pi_0$ so far and run the next $\log^4 n_0$ rounds of $\pi_0$. (If there are fewer than $\log^4 n_0$ rounds in $\pi_0$ remaining after $p$, they treat the remaining rounds as sending all $0$'s.)

At the end of the simulation, Alice has determined a transcript prefix $p_A \subseteq \cE_A$ along with up to $\log^4 n_0$ subsequent edges extending $p_A$. She also has a confidence $c_A \in [0, 1]$. She adds the $\le \log^4 n_0$ edges to $\cE_A$ (ignoring duplicates). Further, if $p_A$ is a complete transcript of length $n_0$, she adds $c_A$ to $\cL_A[p_A]$. Bob does the same.

* At the end of the protocol, let $T_A = \arg\max_{p} \cL_A[p]$ be the transcript with the highest weight in $\cL_A$, and let $w_A = \cL_A[T_A]$. Also, let $w^c_A = \sum_{p \not= T_A} \cL_A[p]$ be the total weight assigned to all the other leaves excluding $T_A$. Then, Alice outputs $T_A$, along with confidence $c_A = \frac{w_A - w^c_A}{\beta}$.

Similarly, Bob outputs the transcript $T_B = \arg\max_{p} \cL_B[p]$ and confidence $c_B = \frac{w_B - w^c_B}{\beta}$, where $w_B = \cL_B[T_B]$ and $w^c_B = \sum_{p \not= T_B} \cL_B[p]$ is the total weight on all the other leaves excluding $T_B$.

Let $\epsilon < 0.25$ and $C_\epsilon \ge 100/\epsilon + 1$. Assume a $(\rho, \epsilon, \mu_\epsilon)$-scaling scheme that simulates noiseless protocols of length $n$ with communication complexity $r_\epsilon(n)$ and computational complexity $T_\epsilon(n)$. Then, the protocol given in Protocol <ref> is a $(\rho, 4\epsilon, e^{-\epsilon n_0 / 10 \log^4 n_0})$-scaling scheme for noiseless protocols of length $n_0$ that has communication complexity $\frac{n_0}{\epsilon \log^4 n_0} \cdot r_{\epsilon}(C_\epsilon \cdot \log^4 n_0)$ and computational complexity $\tilde{O_{\epsilon}}(n_0) \cdot T_\epsilon(C_\epsilon \log^4 n_0)$, assuming that $\mu_\epsilon(C_\epsilon \log^4 n_0) < \frac\epsilon4$.

Clearly, the communication complexity in Protocol <ref> is $\frac{n_0}{\epsilon \log^4 n_0} \cdot r_\epsilon (C_\epsilon \log^4 n_0)$. As for the computational complexity, note that in each iteration, Alice needs to do $T_\epsilon(C_\epsilon \log^4 n_0)$ computations to obtain a transcript $T'$ and a confidence $c'$. She may further have to update $\cL_A[T]$ with the confidence $c'$, for some complete transcript $T$, which can be done in amortized $O(\log L)$ time since a dictionary is roughly implemented by a hash table, where $L$ is an upper bound on the size of $\cL_A$. Finally, at the end of the protocol, she can determine $T_A, w_A, w^c_A$ by making a linear pass through $\cL_A$. Thus, the total computational complexity is $\beta \cdot (T_\epsilon(C_\epsilon \log^4 n_0) + O(\log L)) + \tilde{O}(L)$. Since $L \le \beta$, which follows from the fact that Alice makes at most one value of $\cL_A[p]$ nonzero in each iteration, the total computational complexity is $\tilde{O}(\beta) \cdot T_\epsilon(C_\epsilon \log^4 n_0)$ which is at most $\tilde{O_{\epsilon}}(n_0) \cdot T_\epsilon(C_\epsilon \log^4 n_0)$.

We will now show that our scheme is $(\rho, 4\epsilon, e^{-\epsilon n_0 / 10 \log^4 n_0})$-scaling. First, the consistency property follows because each of the protocols in the $\beta$ iterations are consistent: Alice and Bob only add edges to $\cE_A, \cE_B$ that are consistent with their own input, so only transcripts consistent with their own input can gain weight in $\cL_A, \cL_B$. The rest of this proof will show the scaling properties.

Let $\delta_1, \dots, \delta_\beta$ be the fractional amount of corruption in each of the $\beta$ simulations, so that the total fractional amount of error is $\delta = \frac1\beta \sum_{i = 1}^\beta \delta_i$. Let $T'_{A,1}, \dots, T'_{A,\beta}$ and $c'_{A,1}, \dots, c'_{A,\beta}$ (resp. $T'_{B,1}, \dots, T'_{B,\beta}$ and $c'_{B,1}, \dots, c'_{B,\beta}$) be the transcripts and confidences Alice (resp. Bob) has at the end of each of the $\beta$ simulations.

Denote by $E_i(T'_i)$ denote the event that in the transcript $T'_i$, Alice and Bob correctly determine their longest shared path $\cE_A \cap \cE_B$ and extend it by $\log^4 n_0$ bits (or send $0$'s once the total transcript exceeds length $n_0$).

The following holds for the simulation in the $i$'th iteration:

* If there are at most $\delta_i < (1 - \epsilon) \cdot \rho$ errors, then

\[
\Pr \left[ E_i(T'_{A,i}) ~\wedge~ E_i(T'_{B,i}) ~\wedge~ c'_{A,i}, c'_{B,i} \ge 1 - \frac{\delta_i}{\rho} - \epsilon \right]
\ge 1 - \mu_\epsilon(C_\epsilon \cdot \log^4 n_0) - 2^{-c \log^4 n_0}.
\]

* If there are at least $\delta_i \ge (1 - \epsilon) \cdot \rho$ errors, then

\begin{align*}
\Pr \left[ \left( \neg E_i(T'_{A,i}) ~\wedge~ c'_A > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \vee \left( \neg E_i(T'_{B,i}) ~\wedge~ c'_B > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \right] \\
\le \mu_\epsilon(C_\epsilon \cdot \log^4 n_0) + 2^{-c \log^4 n_0}.
\end{align*}

First, suppose that $\delta_i < (1 - \epsilon) \cdot \rho$. Let $T^*_i$ denote the noiseless protocol in the $i$'th simulation. Note that with probability $e^{\log^4 n_0 / \epsilon}$, $T^*_i$ may not correctly determine Alice and Bob's longest shared path. In particular,

\begin{align*}
\Pr&~ \left[
\neg \left( E_i(T'_{A,i}) ~\wedge~ E_i(T'_{B,i}) ~\wedge~ c'_{A,i}, c'_{B,i} \ge 1 - \frac{\delta_i}{\rho} - \epsilon \right)
\right]\\
\le&~ \Pr \left[
\neg E_i(T^*_i)
\right]
+ \Pr \left[
\neg \left( T'_{A,i} = T'_{B,i} = T^*_i ~\wedge~ c'_{A,i}, c'_{B,i} \ge 1 - \frac{\delta_i}{\rho} - \epsilon \right)
\right] \\
\le&~ 2^{\log^4 n_0 / \epsilon} + \mu_\epsilon(C_\epsilon \cdot \log^4 n_0)
\end{align*}

by Theorem <ref> and Definition <ref>.

On the other hand, if $\delta_i \ge (1 - \epsilon) \cdot \rho$, it holds that

\begin{align*}
&~ \Pr \left[ \left( \neg E_i(T'_{A,i}) ~\wedge~ c'_A > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \vee \left( \neg E_i(T'_{B,i}) ~\wedge~ c'_B > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \right] \\
&\le \Pr [ \neg E_i(T^*_i) ] + \Pr \left[ \left( T'_{A,i} \not= T^*_i ~\wedge~ c'_A > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \vee \left( T'_{B,i} \not= T^*_i ~\wedge~ c'_B > \frac{\delta_i}{\rho} - 1 + \epsilon \right) \right] \\
&\le 2^{\log^4 n_0/\epsilon} + \mu_\epsilon(C_\epsilon \cdot \log^4 n_0),
\end{align*}

where the second line follows from considering the cases where $\neg E_i(T^*_i)$ and $E_i(T^*_i)$, and the third line follows from Theorem <ref> and Definition <ref>.

Let $I \subseteq [\beta]$ denote the iterations in which $< (1-\epsilon) \cdot \rho$ of the scheme was corrupted.

With probability $1 - e^{-\epsilon^2 \beta / 10}$, for all except at most $\epsilon \cdot \beta$ values of $i \in [\beta]$, it holds that either:

* $i \in I$ and $E_i(T'_{A,i}) ~\wedge~ E_i(T'_{B,i}) ~\wedge~ c'_{A,i}, c'_{B,i} \ge 1 - \frac{\delta_i}{\rho} - \epsilon$,

* $i \in [\beta] \backslash I$ and $\left( E_i(T'_{A,i}) \vee c'_A \le \frac{\delta_i}{\rho} - 1 + \epsilon \right) \wedge \left( E_i(T'_{B,i}) \vee c'_B \le \frac{\delta_i}{\rho} - 1 + \epsilon \right)$.

By Lemma <ref>, one of the two conditions holds for every $i \in [\beta]$ with probability at least $1 - 2^{-\log^4 n_0 / \epsilon} - \mu_\epsilon (C_\epsilon \cdot \log^4 n_0)$. This means that the expected number of $i$ satisfying one of the two conditions is $\varpi \ge (1 - 2^{-\log^4 n_0 / \epsilon} - \mu_\epsilon(C_\epsilon \log^4 n_0)) \cdot \beta$.

Let $X$ denote the number of $i \in [\beta]$ satisfying one of the two conditions. By Chernoff,

\begin{align*}
\Pr [X < (1 - \epsilon) \cdot \beta]
\le \Pr [X < (1 - \epsilon/2) \cdot \varpi]
\le e^{-\epsilon^2 \varpi / 8}
\le e^{-\epsilon^2 \beta / 10},
\end{align*}

where the first and last inequalities follow from the fact that $2^{-\log^4 n_0 / \epsilon} + \mu_\epsilon(C_\epsilon \log^4 n_0) \le 2^{-1/\epsilon} + \mu_\epsilon(C_\epsilon \log^4 n_0) < \frac\epsilon4 + \frac\epsilon4 = \frac\epsilon2$, so $(1 - \epsilon/2) \cdot \beta < \varpi$. In particular, the first inequality follows from $(1 - \epsilon) \beta < (1 - \epsilon/2)^2 \beta < (1 - \epsilon/2) \varpi$, and the last inequality follows from $0.8 \beta < (1 - \epsilon/2) \beta < \varpi$.

Let $\Gamma \subseteq I$ be the set of all $i$ satisfying <ref>, and let $\Lambda \subseteq [\beta] \backslash I$ be the set of all $i$ satisfying <ref>. Note that after the first $\frac{n_0}{\log^4 n_0}$ iterations in $\Gamma$, Alice and Bob are both guaranteed to have all edges in the correct transcript $\cT$ in their edge lists $\cE_A$ and $\cE_B$. After that point, in every iteration in $\Gamma$, Alice and Bob both determine the correct transcript $\cT = \cE_A \cap \cE_B$ and add $c'_{A,i}$ (resp. $c'_{B,i}$) to $\cL_A[\cT]$ (resp. $\cL_B[\cT]$). This means that at the end of the protocol,

\[
\cL_A[\cT] \ge \sum_{i \in \Gamma} c'_{A,i} - \frac{n_0}{\log^4 n_0}
\ge (1-\epsilon) \cdot |\Gamma| - \frac1\rho \cdot \sum_{i \in \Gamma} \delta_i - \frac{n_0}{\log^4 n_0},
\]

and similarly

\[
\cL_B[\cT] \ge (1-\epsilon) \cdot |\Gamma| - \frac1\rho \cdot \sum_{i \in \Gamma} \delta_i - \frac{n_0}{\log^4 n_0}.
\]

Meanwhile, for each iteration in $\Lambda$, a weight of at most $c'_{A,i}$ (resp. $c'_{B,i}$) is added to a wrong leaf. Furthermore, a weight of at most $1$ is added to a wrong leaf for each iteration in $[\beta] \backslash (\Gamma \cup \Lambda)$, which by Lemma <ref> has size at most $\epsilon \beta$ with probability $1 - e^{-\epsilon^2 \beta / 10}$. Thus, with probability $1 - e^{-\epsilon^2 \beta / 10}$, the total weight on all the wrong leaves in Alice's tree is at most

\[
\le \sum_{i \in \Lambda} c'_{A,i} \cdot \mathbbm{1}[T'_{A,i} \not= T^*_i]
+ \sum_{i \in [\beta] \backslash (\Gamma \cup \Lambda)} 1
\le \frac1\rho \cdot \sum_{i \in \Lambda} \delta_i - (1 - \epsilon) \cdot |\Lambda| + \epsilon \beta,
\]

and simultaneously the total weight on all the wrong leaves in Bob's tree is at most

\[
\le \sum_{i \in \Lambda} c'_{B,i} \cdot \mathbbm{1}[T'_{B,i} \not= T^*_i]
+ \sum_{i \in [\beta] \backslash (\Gamma \cup \Lambda)} 1
\le \frac1\rho \cdot \sum_{i \in \Lambda} \delta_i - (1 - \epsilon) \cdot |\Lambda| + \epsilon \beta.
\]

Then, with probability $1 - e^{-\epsilon^2 \beta / 10}$, the difference between the weight on the correct leaf and the combined weight on all the wrong leaves, for both Alice and Bob, is

\begin{align*}
\cL_A[\cT] &- \sum_{T \not= \cT} \cL_A[T] ~\text{(resp.}~\cL_B[\cT] - \sum_{T \not= \cT} \cL_B[T]\text{)}\\
&\ge \left[ (1 - \epsilon) \cdot |\Gamma| - \frac1\rho \cdot \sum_{i \in \Gamma} \delta_i - \frac{n_0}{\log^4 n_0} \right]
- \left[ \frac1\rho \cdot \sum_{i \in \Lambda} \delta_i - (1 - \epsilon) \cdot |\Lambda| + \epsilon \beta \right] \\
&= (1 - \epsilon) \cdot (|\Gamma| + |\Lambda|) - \epsilon \beta - \frac1\rho \cdot \sum_{i \in \Gamma \cup \Lambda} \delta_i - \frac{n_0}{\log^4 n_0} \\
&\ge (1 - \epsilon) \cdot (\beta - \epsilon \beta) - \epsilon \beta - \frac{\delta \beta}{\rho} - \epsilon \beta \\
&\ge \left( 1 - \frac\delta\rho - 4\epsilon \right) \cdot \beta, \numberthis \label{eqn:difference-weights}
\end{align*}

where we used that $\beta = \frac{n_0}{\epsilon \log^4 n_0}$ and that $\sum_{i \in \Gamma \cup \Lambda} \delta_i \le \sum_{i \in [\beta]} \delta_i = \delta \beta$.

In particular, if $\delta < (1 - \frac\delta\rho - 4\epsilon) \cdot \rho$, then with probability $1 - e^{-\epsilon^2 \beta / 10}$, both Alice and Bob output $T_A = T_B = \cT$ and confidence $c_A, c_B \ge 1 - \frac\delta\rho - 4\epsilon$.

On the other hand, Equation <ref> tells us that with probability $1 - e^{-\epsilon^2 \beta/10}$, for both Alice and Bob, for any incorrect leaf $T_0$, the total weight on $T_0$ minus the combined weight on all the other leaves is at most

\[
\le \left( \frac\delta\rho - 1 + 4\epsilon \right) \cdot \beta,
\]

since $\cL_A[T_0] \le \sum_{T \not= \cT} \cL_{A}[T]$, and $\sum_{T \not= T_0} \cL_A[T] \ge \cL_A[\cT]$ (and same for Bob). Thus, in the case that $\delta > (1 - \frac\delta\rho - 4\epsilon) \cdot \rho$ of the entire protocol is corrupted, it holds with probability $1 - e^{-\epsilon^2 \beta / 10}$ that either $T_A = \cT$, or $T_A \not= \cT$ and $c_A \le \frac\delta\rho - 1 + 4\epsilon$, and same for Bob.

It follows that Protocol <ref> is $(\rho, 4\epsilon, e^{-\epsilon^2 \beta/10}) = (\rho, 4\epsilon, e^{-\epsilon n_0 / 10 \log^4 n_0})$-scaling.

§ LAYERED CODES

In this section, we introduce sensitive layered codes, which are a generalization and strengthening of list tree codes to codes on layered graphs. List tree codes were first introduced in [1] as an analogue of list-decodable error correcting codes for the tree code setting. Sensitive layered codes are instead defined on certain graphs, and have list size $1$ for most locations.

We first define suffix distance.

For two strings $x, y \in \Sigma^n$, we define the suffix distance as follows:

\[
\Delta_{sfx}(x, y) = \max_{0 \le i \le n-1} \frac{\Delta(x[i+1:n], y[i+1:n])}{n-i}.
\]

§.§ Layered Codes

Let $\Sigma$ be an alphabet. A layered graph over  $\Sigma$ of depth $n$ is a directed graph $G$ that satisfies the following properties:

* The vertices of $G$ can be split up into layers $0,1,\dots, n$. There is exactly one vertex in layer $0$.

* Each vertex in layer $i < n$ has out-degree exactly $|\Sigma|$: it has $|\Sigma|$ children in layer $i+1$, where the $|\Sigma|$ out-edges are associated with not necessarily distinct elements of $\Sigma$.

If $G$ is a layered graph over $\Sigma_{in}$ of depth $n$, note that any path $p$ in $G$ from the root node to a vertex in layer $i$ can be associated with a string $\in \Sigma_{in}^i$. Likewise, any string $\in \Sigma_{in}^i$ corresponds to a unique path in $G$ from the root node to a vertex in layer $i$. We will interchangeably refer to the path $p$ or the associated string $\in \Sigma_{in}^i$. Furthermore, for any string $p \in \Sigma_{in}^i$, we use $v(p)$ to denote the vertex at the end of $p$.

Let $G$ be a layered graph over $\Sigma_{in}$ of depth $n$. A layered code $\PikC$ of $G$ with the alphabet $\Sigma_{out}$ is an assignment of elements of $\Sigma_{out}$ to the edges of $G$. We refer to such an assignment as a $(G, \Sigma_{out})$-code.

For any subgraph $H\subseteq G$, we define $\PikC(H)$ to be the subgraph $H$ inheriting labels from $\PikC$. Specifically, for a rooted path $p \in \Sigma_{in}^i$, $\PikC(p)\in \Sigma_{out}^i$ is the string of $i$ labels of the edges in $p$.

§.§ Prefix Trees

For any $(G,\Sigma_{out})$-code, any $\epsilon$, and any word $w \in \Sigma_{in}^n$, let the list $L_i(\PikC, w, \epsilon)$ be the list of nodes in layer $i$ that are the endpoint of at least one path whose encoding under $\PikC$ is close to the prefix of $w$ of length $i$ in their suffix distance. That is,

\[
L_i(\PikC, w, \epsilon) = \{ v(p) : p \in \Sigma_{in}^i ~\text{s.t.}~ \Delta_{sfx}(\PikC(p), w[1:i]) < 1 - \epsilon \}.
\]

We also write $L(\PikC, w, \epsilon) = \cup_{i=1}^n L_i(\PikC, w, \epsilon)$.

Consider a subset $S \subseteq L(\PikC, w, \epsilon)$. For each $v \in S$, we pick a path $p$ from the root to $v$ satisfying $\Delta_{sfx} ( \PikC(p), w[1:|p|]) < 1 - \epsilon$. If these paths form a rooted tree, we call their union a prefix tree of $S$. We denote by $\PT(\PikC, w, \epsilon)$ the set of all prefix trees of all subsets of $L(\PikC, w, \epsilon)$.

Fix $w \in \Sigma_{out}^n$ and $\epsilon > 0$. For any subset $S \subseteq L(\PikC, w, \epsilon)$, there is a prefix tree of $S$.

For a path $q$ of length $k$, we define the deficit of $q$, denoted $\mathsf{deficit}(q)$, to be $\max_{0 \le j < k} \left[ \Delta(\PikC(q)[j+1:k], w[j+1:k]) - (1 - \epsilon) \cdot (k-j) \right]$. For a path $p$ of length $i$, we say that the excess of $p$ at $k \le i$ is $(1 - \epsilon) \cdot (i - k) - \Delta(\PikC(p)[k+1:i], w[k+1:i])$, denoted $\mathsf{excess}_k(p)$. Note that for any path $p$ for which $v(p) \in L_i(\PikC, w, \epsilon)$, it holds that $\mathsf{excess}_k(p) > 0$ for any $k \le i$.

Furthermore, we claim that for any $p \in \Sigma_{in}^i$ such that $v(p) \in L_i$, letting $p'$ denote the path obtained by replacing the first $k$ edges by $q \in \Sigma_{in}^k$, we have that $\Delta_{sfx}(\PikC(p'), w[1:i]) < 1 - \epsilon$ iff $\mathsf{deficit}(q) < \mathsf{excess}_k(p)$. To see this, we can write

\begin{align*}
\Delta_{sfx} (\PikC(p'), w[1:i])
= \max \left\{
\begin{aligned}
\Delta_{sfx} ( \PikC(p)[k+1:i], w[k+1:i] ), \\ \max_{0\le j < k}\frac{\Delta(\PikC(p)[k+1:i], w[k+1:i]) + \Delta(q[j+1:k], w[j+1:k]))}{i-j}
\end{aligned} \right\}.
\end{align*}

Note that $\Delta_{sfx} ( \PikC(p)[k+1:i], w[k+1:i] ) < 1 - \epsilon$ because $v(p) \in L_i$. Thus, $\Delta_{sfx}(\PikC(p'), w[1:i]) < 1 - \epsilon$ iff

\[
\Delta(\PikC(p)[k+1:i], w[k+1:i]) + \Delta(q[j+1:k], w[j+1:k])) < (1-\epsilon) \cdot (i-j)
\]

for all $0 \le j < k$, or equivalently,

\[
\mathsf{deficit}(q) < \mathsf{excess}_k(p).
\]

Now, given a selection of paths $\{ p(v) \}_{v \in S}$, where $p(v)$ connects the root to $v$, for each $k \in [n]$ define $\Lambda_k(p)$ to be the set of vertices $y \in G$ in layer $k$ such that there are two paths $p(v)$ and $p(v')$, where $v \not= v' \in S$, for which $v(p(v)[1:k]) = v(p(v')[1:k]) = y$ but $p(v)[1:k] \not= p(v')[1:k]$. We define $\Psi(p)$ to be $(k_{max}, |\Lambda_{k_{max}}(p)|)$, with the lexicographical ordering, where $k_{max}$ is the largest layer $k$ for which $\Lambda_k(p)$ is nonempty.

In order to construct a prefix tree of $S$, we begin by choosing a path $p(v)$ from the root to $v$ for each $v \in S$. Next, we perform an operation to $p$ that decreases $\Psi(p)$, while preserving that $p$ satisfies $\Delta_{sfx}(\PikC(p(v)), w[1:|p(v)|]) < 1 - \epsilon$ for all $v \in S$. The operation we perform is as follows: Choose $y_{max} \in \Lambda_{k_{max}}(p)$. Furthermore, let $v_1, \dots, v_m \in S$ be such that $v(p(v_\iota)[1:k]) = y_{max}$. Define $q_\iota := p(v_\iota)[1:k]$ for each $\iota \in [m]$. Let $\hat{\iota} = \arg\min_{\iota \in [m]} \mathsf{deficit}(q_\iota)$, and let $q = q_{\hat{\iota}}$. Then, for each $\iota \in [m]$, we replace $p(v_\iota)$ with the path $p'(v_\iota) = q || p(v_\iota)[k+1:|p(v_\iota)|]$. Since $\mathsf{deficit}(q) \le \mathsf{deficit}(q_\iota)$, it holds that $\Delta_{sfx}(\PikC(p'(v_\iota)), w[1:|p'(v_\iota)|]) < 1-\epsilon$ for all $\iota \in [m]$. (For all other $v \in S$ where $p(v)$ doesn't pass through $y_{max}$, we define $p'(v) = p(v)$.)

Note that $\Lambda_k(p')$ where $k > k_{max}$ must still be empty, as we have only altered edges in layers at most $k_{max}$. Furthermore, $|\Lambda_{k_{max}}(p')|$ is strictly less than $|\Lambda_{k_{max}}(p)|$, since we have replaced paths going through $y_{max}$ with paths going through $y_{max}$ so no new intersections in layer $k_{max}$ were created, and we have removed $y_{max}$ from $\Lambda_{k_{max}}(p)$. Thus, $\Psi(p') < \Psi(p)$. Also note that as long as $\Psi(p) > (0,0)$, we can continue this operation, so eventually $\Psi(p) = (0,0)$, at which point the union of $p(v), v \in S$ is a tree.

For a subgraph $H$ of $G$ of depth at most $|w|$, we denote by $w(H)$ the graph where we write $w[i]$ on all edges at depth $i$. For a $(G, \Sigma_{out})$-code $\PikC$, recall that $\PikC(H)$ is the subgraph $H$ inheriting labels from $\PikC$. For two labelings $w$ and $\PikC$ of a subgraph $H$, we define $agr(w(H), \PikC(H))$ to be the number of edges of $H$ for which the labels are the same.

For any $w \in \Sigma_{out}^n$ and $\epsilon > 0$, and for any $PT \in \PT(\PikC, w, \epsilon)$,

\[
agr(\PikC(PT), w(PT)) > \epsilon |PT|.
\]

First, note that by definition of $L(\PikC, w, \epsilon)$, for any path $p$ ending at $v \in L(\PikC, w, \epsilon)$ and not necessarily starting at the root, it holds that $agr(\PikC(p), w(p)) > \epsilon |p|$. We call this Property A.

We prove the lemma by induction on the number of leaves. If $PT$ has only $1$ leaf, then it is a path from root to leaf, and by Property A, $agr(\PikC(PT), w(PT)) > \epsilon |PT|$. Now, if $PT$ has more than one leaf, let $p$ be a branch of $PT$ (i.e. a path from a vertex $v_0$ to a leaf $v$, where $v_0$ has more than one child). Then $PT \backslash p$ has one fewer leaf than $PT$, and by inductive hypothesis we have

\[
agr(\PikC(PT \backslash p), w(PT \backslash p) > \epsilon ( |PT| - |p| ).
\]

Furthermore, by Property A, we have that $agr(\PikC(p), w(p)) > \epsilon |p|$. Therefore,

\[
agr(\PikC(PT), w(PT)) = agr(\PikC(PT \backslash p), w(PT \backslash p) + agr(\PikC(p), w(p)) > \epsilon |PT|.
\]

§.§ Sensitive Layered Codes

Let $G$ be a layered graph over $\Sigma_{in}$ of depth $n$. A $\epsilon$-sensitive layered code for $G$ and alphabet $\Sigma_{out}$ is a $(G, \Sigma_{out})$-code such that for all $w \in \Sigma_{out}^n$ and all $PT \in \PT(\PikC, w, \epsilon)$,

\[
agr(\PikC(PT), w(PT)) \le (1 + \epsilon) n. \numberthis \label{eqn:agr-condition}
\]

For $\epsilon \in (0, \frac12)$ and a layered graph $G$ over $\Sigma_{in}$ with depth $n \ge \frac{2}{1-\epsilon}$, let $|\Sigma_{out}| > 2 |\Sigma_{in}|)^{6/\epsilon^2}$. Then, a random $(G, \Sigma_{out})$-code is a $\epsilon$-sensitive layered code on $G$ with alphabet $\Sigma_{out}$ with probability at least $1 - 2^{-n/4\epsilon}$.

The proof of Theorem <ref> essentially follows from the proof of Theorem 22 in [1]. To prove it, we will need the following two lemmas:

If $G$ is a layered graph over $\Sigma_{in}$, there exist at most $(|\Sigma_{in}|+1)^{2s}$ rooted subtrees of $G$ of size $s$.

Consider the path obtained by conducting a DFS on a rooted subtree, where each symbol indicates which child to go to, and $|\Sigma_{in}|+1$ indicates to go back up the edge traversed downwards to get to the current vertex (note that this edge is unique since we only traverse a subtree). Then, each edge in the subtree is traversed twice. Thus, the number of rooted subtrees of $G$ is at most $(|\Sigma_{in}| + 1)^{2s}$.

For any $w \in \Sigma_{out}^n$ and for any collection $PT$ of $s$ edges of $G$, it holds that

\[
Pr [ agr(\PikC(PT), w(PT)) \ge \epsilon s ] \le |\Sigma_{out}|^{-\epsilon s} \binom{s}{\epsilon s} \le |\Sigma_{out}|^{-\epsilon s} 2^s,
\]

where randomness is taken over the random choice of layered code $\PikC$ on $G$ with $\Sigma_{out})$.

The first inequality follows from the union bound over all possible locations where $\PikC(PT)$ and $w(PT)$ agree, and the second inequality follows from $\binom{s}{\epsilon s} \le 2^s$.

If $w \in \Sigma_{out}^n$ violates (<ref>), then there is a prefix tree $PT$ of a subset $S \subseteq L(\PikC, w, \epsilon)$ such that $agr(\PikC(PT), w(PT)) > \max \{ \epsilon |PT|, (1 + \epsilon) n \}$, where $agr(\PikC(PT), w(PT)) > \epsilon |PT|$ is given by Lemma <ref>. To show that such $w$ does not exist, we will show that with high probability over the choice of a random $(G, \Sigma_{out})$-code, $agr(\PikC(PT), w(PT)) \le \max \{ \epsilon |PT|, (1 + \epsilon) n \}$ for all rooted subtrees $PT$ and $w \in \Sigma_{out}^n$. It is enough to prove this claim for all $|PT| \ge (1 + \frac1\epsilon) n$, since if $|PT| < (1 + \frac1\epsilon) n$, then we can extend $PT$ to a tree $PT'$ of size $(1 + \frac1\epsilon) n$ and for this subtree it will hold that $agr(\PikC(PT'), w(PT')) \le (1 + \epsilon) n$ and thus $agr(\PikC(PT), w(PT)) \le (1 + \epsilon) n$. We thus seek to show that with high probability over the choice of a random layered code, $agr(\PikC(PT), w(PT)) \le \epsilon |PT|$ for all rooted subtrees $PT$ of size $\ge (1 + \frac1\epsilon) n$ and $w \in \Sigma_{out}^n$.

Using Lemmas <ref> and <ref>, we union bound over all possible trees of size $\ge (1 + \frac1\epsilon) n =: s$ and words $w$ to see that the probability there exists $|PT| \ge (1 + \frac1\epsilon) n$, $w \in \Sigma_{out}^n$ for which $agr(\PikC(PT), w(PT)) \ge \epsilon s$ is upper bounded by

\begin{align*}
\sum_{s = (1 + \frac1\epsilon) n}^\infty |\Sigma_{out}|^{-\epsilon s} 2^s \cdot (|\Sigma_{in}| + 1)^{2s} \cdot |\Sigma_{out}|^n
&= |\Sigma_{out}|^n \sum_{s = (1 + \frac1\epsilon) n}^\infty \left( \frac{2 \cdot (|\Sigma_{in}| + 1)^2}{|\Sigma_{out}|^\epsilon} \right)^s \\
&\le |\Sigma_{out}|^n \sum_{s = (1 + \frac1\epsilon) n}^\infty \left( \frac{8 \cdot |\Sigma_{in}|^2}{|\Sigma_{out}|^\epsilon} \right)^s
\end{align*}

Since $|\Sigma_{out}| > (2 |\Sigma_{in}|)^{6/\epsilon^2} > 8 |\Sigma_{in}|^2$, this is upper bounded by

\begin{align*}
\le |\Sigma_{out}|^n \left( \frac{8 \cdot |\Sigma_{in}|^2}{|\Sigma_{out}|^\epsilon} \right)^{(1 + \frac1\epsilon) n - 1}
&= \frac{(8 \cdot |\Sigma_{in}|^2)^{(1 + \frac1\epsilon) n - 1}}{|\Sigma_{out}|^{\epsilon n - \epsilon}} \\
&\le \frac{(8 \cdot |\Sigma_{in}|^2)^{(1 + \frac1\epsilon) n - 1}}{(2\cdot |\Sigma_{in}|)^{6(n-1)/\epsilon}} \\
&\le \frac{(8 \cdot |\Sigma_{in}|^2)^{(1 + \frac1\epsilon) n - 1}}{(8 \cdot |\Sigma_{in}|^2)^{2(n-1)/\epsilon}} \\
&\le \left( 8 \cdot |\Sigma_{in}|^2 \right)^{-((1-\epsilon) n - 2)/\epsilon} \\
&\le 2^{-n/4\epsilon},
\end{align*}

where in the last line we use that $\epsilon < \frac12$ and $(1-\epsilon) n \ge 2$.

§.§ Decoding

Sensitive $(G, \Sigma_{out})$ codes will be useful for us because they guarantee that for most locations $i$ on which $\PikC(x)$ and $w$ agree, $w[1:i]$ decodes to $v(x[1:i])$. First, we define decoding.

Given an $\epsilon$-sensitive-$(G, \Sigma_{out})$-code $\PikC$, we define $\PikCDec$ to be the algorithm that takes as input a string $w \in \Sigma_{out}^i$ and outputs $v \in G$ such that there exists a path $p \in \Sigma_{in}^{i}$ satisfying $\Delta(\PikC(p), w) < 1 - \epsilon$ if exactly one such $v$ exists, and $\perp$ otherwise.

The main theorem of this section is the following:

For every $\epsilon, n$, for any layered graph over $\Sigma_{in}$ of depth $n$ and any $\epsilon$-sensitive-$(G, \Sigma_{out})$-code $\PikC : \Sigma_{in}^n \to  \Sigma_{out}^n$, and for any $x \in \Sigma_{in}^n$ and $w \in \Sigma_{out}^n$, let $J$ be the set of indices where $\PikC(x)[i] = w[i]$. For all but at most $2\epsilon n$ values of $i \in J$, it holds that $\PikCDec(w[1:i]) = v(x[1:i])$.

We defer the proof of Theorem <ref> to after we state a few lemmas.

Given an $\epsilon$-sensitive-$(G, \Sigma_{out})$-code $\PikC$, for any $w \in \Sigma_{out}^n$ and $\epsilon > 0$, it holds that $|L_i(\PikC, w, \epsilon)| \le 1$ for at least $(1 - \epsilon) n$ values of $i \le n$.

Given $w$, we construct $w'$ as follows. Pick a prefix tree $PT$ of $L(\PikC, w, \epsilon)$. For every $i \le n$, define $PT_i(w)$ to be the set of edges in the $i$'th layer of $PT$. If for all $e \in PT_i(w)$ we have that $\PikC(e) \not= w[i]$, then set $w'[i]$ to be $\PikC(e)$ for some arbitrary $e \in PT_i(w)$. Otherwise, set $w'[i] = w[i]$.

Notice that $L(\PikC, w, \epsilon) \subseteq L(\PikC, w', \epsilon)$, since the only indices of $w$ that were changed were those that did not agree with any of the labels of $PT$ in the corresponding layer, so for any path $p(v) \subseteq PT, v \in L_i(\PikC, w, \epsilon)$, it holds that $\Delta_{sfx}(\PikC(p(v)), w'[1:|p(v)|]) \le \Delta_{sfx}(\PikC(p(v)), w[1:|p(v)|]) < 1 - \epsilon$. This means that $PT \in \PT(\PikC, w', \epsilon)$. But by the definition of an $\epsilon$-sensitive-$(G, \Sigma_{out})$-code (Definition <ref>),

\[
agr(\PikC(PT), w'(PT))\leq (1 + \epsilon) n.
\]

On the other hand, we constructed $w'$ so that in each layer $i$, there is at least one edge on which $\PikC$ and $w'$ agree. Therefore, the number of layers in which there is more than $1$ edge on which $\PikC$ and $w'$ agree is $\le \epsilon n$. In other words, the number of layers in which there is at most $1$ edge on which $\PikC$ and $w'$ agree is at least $(1-\epsilon) n$. Let this set of layers be $I \subseteq [n]$.

Finally, note that for any vertex $v \in L_i(\PikC, w, \epsilon)$ and associated path $p(v) \subseteq PT$, it must hold that $\PikC(p(v))[i] = w[i] = w'[i]$ (otherwise the suffix distance of $\PikC(p(v))$ to $w$ is $1$), so for each of the $\ge (1-\epsilon) n$ layers in $I$, there is at most $1$ vertex $v \in L_i(\PikC, w, \epsilon)$.

For any $r, s \in \Sigma^n$, if $\Delta(r, s) = \beta n$, then there exists a set of indices $I \subseteq [n]$ of size $|I| \ge (1 - \beta/\alpha)n$ such that for any $i \in I$,

\[
\Delta_{sfx}(r[1:i], s[1:i]) < \alpha.
\]

By Lemma <ref>, there exists a set of indices $I \subseteq [n]$ of size $|I| \ge (1 - \frac{1 - |J|/n}{1 - \epsilon}) n = \frac{|J| - \epsilon n}{1 - \epsilon} \ge |J| - \epsilon n$ such that for any $i \in I$, $\Delta_{sfx}(\PikC(x)[1 : i], w[1 : i]) < 1 - \epsilon$. Note also that $I \subseteq J$, since if $\PikC(x)[i] \not= w[i]$, then $\Delta_{sfx}(\PikC(x)[1:i], w[1:i]) = 1$.

Furthermore, by Lemma <ref>, it holds that $|L_i(\PikC, w, \epsilon)| > 1$ on at most $\epsilon n$ values. Thus, there are at least $|J| - 2\epsilon n$ values of $J$ for which $\PikCDec(w[1:i]) = v(x[1:i])$.

In this section, we defined sensitive layered codes on finite-depth layered graphs. However, our proofs extend straightforwardly to give sensitive layered codes on layered graphs of infinite depth. For an infinite graph, sensitivity means that the restriction of the code to any depth $n$ (above a certain threshold) should be a sensitive layered code. It is straightforward via a union bound to see that a random layered code on an infinite layered graph will, with positive probability, satisfy sensitivity.

§.§ Discussion

In this section, we have only defined and proven properties of layered codes that are useful in our protocol. However, layered codes also serve as a generalization of tree codes that may be of independent interest, and we hope to see future work further generalizing the results of tree codes to this context. We propose a few problems to guide the future study of layered codes.

*  We have shown that sensitive layered codes exist, but have not addressed the analogue of tree codes. Do layered codes exist on any layered graph over $\Sigma$? Specifically, for any $\epsilon$ is there an assignment of the edges of a layered graph over $\Sigma$ to a larger alphabet $\Sigma_{out}$ such that for any two words $x,y\in \Sigma^n$ such that $v(x)\neq v(y)$, the suffix distance $\Delta_{sfx}(x,y)>1-\epsilon$?

* Our protocol is one in which layered codes are necessary, and tree codes are not strong enough. Are there other contexts where this is the case? One possible use case may be in low memory settings, where a party cannot remember the full history of the messages they have sent, and so needing only to remember the vertex of the graph they are on may be useful.

* Do tree codes beyond layered graphs? For example, does the definition of suffix distance generalize to any directed graph? Does Theorem <ref> generalize to a more general context? Does Question <ref> generalize?

§ POSITIVE RATE SCHEME RESILIENT TO $\FRAC16$ ERRORS

§ ACKNOWLEDGMENTS

Rachel Yun Zhang is supported by an Akamai Presidential Fellowship.

[1]
Mark Braverman and Klim Efremenko.
List and Unique Coding for Interactive Communication in the Presence
of Adversarial Noise.
In 2014 IEEE 55th Annual Symposium on Foundations of Computer
Science (FOCS), pages 236–245, Los Alamitos, CA, USA, oct 2014. IEEE
Computer Society.

[2]
Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky.
Coding for Interactive Communication Correcting Insertions and
IEEE Transactions on Information Theory, PP, 08 2015.

[3]
Zvika Brakerski and Yael Tauman Kalai.
Efficient Interactive Coding against Adversarial Noise.
In 2012 IEEE 53rd Annual Symposium on Foundations of Computer
Science, pages 160–166, 2012.

[4]
Zvika Brakerski and Moni Naor.
Fast Algorithms for Interactive Coding.
In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA '13, page 443–456, USA, 2013. Society for
Industrial and Applied Mathematics.

[5]
Mark Braverman and Anup Rao.
Towards Coding for Maximum Errors in Interactive Communication.
In Proceedings of the Forty-Third Annual ACM Symposium on Theory
of Computing, STOC '11, page 159–166, New York, NY, USA, 2011. Association
for Computing Machinery.

[6]
Mark Braverman.
Towards Deterministic Tree Code Constructions.
In Proceedings of the 3rd Innovations in Theoretical Computer
Science Conference, ITCS '12, page 161–167, New York, NY, USA, 2012.
Association for Computing Machinery.

[7]
Inbar Ben-Yaacov, Gil Cohen, and Tal Yankovitz.
Explicit binary tree codes with sub-logarithmic size alphabet.

[8]
Gil Cohen, Bernhard Haeupler, and Leonard J. Schulman.
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet.
In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory
of Computing, STOC 2018, page 535–544, New York, NY, USA, 2018.
Association for Computing Machinery.

[9]
Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, and Maxwell Young.
Interactive Communication with Unknown Noise Rate, 2015.

[10]
Klim Efremenko, Ran Gelles, and Bernhard Haeupler.
Maximal Noise in Interactive Communication Over Erasure Channels and
Channels With Feedback.
IEEE Trans. Inf. Theory, 62(8):4575–4588, 2016.

[11]
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena.
Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or
why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$.
In 2020 IEEE 61st Annual Symposium on Foundations of Computer
Science (FOCS), pages 470–481, 2020.

[12]
Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman.
Optimal Coding for Streaming Authentication and Interactive
IEEE Transactions on Information Theory, 61(1):133–145, 2015.

[13]
Ran Gelles.
Coding for Interactive Communication: A Survey.
Foundations and Trends® in Theoretical Computer Science,
13:1–161, 01 2017.

[14]
Mohsen Ghaffari and Bernhard Haeupler.
Optimal Error Rates for Interactive Coding II: Efficiency and List
Proceedings - Annual IEEE Symposium on Foundations of Computer
Science, FOCS, 12 2013.

[15]
Ran Gelles and Bernhard Haeupler.
Capacity of Interactive Communication over Erasure Channels and
Channels with Feedback.
SIAM Journal on Computing, 46:1449–1472, 01 2017.

[16]
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, and Avi Wigderson.
Towards Optimal Deterministic Coding for Interactive
Communication, pages 1922–1936.

[17]
Ran Gelles and Siddharth Iyer.
Interactive coding resilient to an unknown number of erasures.
arXiv preprint arXiv:1811.02527, 2018.

[18]
Ran Gelles, Ankur Moitra, and Amit Sahai.
Efficient and Explicit Coding for Interactive Communication.
pages 768–777, 10 2011.

[19]
Meghal Gupta and Rachel Yun Zhang.
The Optimal Error Resilience of Interactive Communication Over
Binary Channels.
In Symposium on Theory of Computing, STOC 2012, New York, NY,
USA, June 20 - June 24, 2022, STOC '22. ACM, 2022.

[20]
Bernhard Haeupler.
Interactive Channel Capacity Revisited.
In 55th IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages
226–235, 2014.

[21]
R. W. Hamming.
Error detecting and error correcting codes.
The Bell System Technical Journal, 29(2):147–160, 1950.

[22]
Bernhard Haeupler and Amirbehshad Shahrasbi.
Synchronization Strings: Codes for Insertions and Deletions
Approaching the Singleton Bound.
J. ACM, 68(5), sep 2021.

[23]
Cristopher Moore and Leonard J. Schulman.
Tree Codes and a Conjecture on Exponential Sums.
In Proceedings of the 5th Conference on Innovations in
Theoretical Computer Science, ITCS '14, page 145–154, New York, NY, USA,
2014. Association for Computing Machinery.

[24]
Pavel Pudlák.
Linear tree codes and the problem of explicit constructions.
Linear Algebra and its Applications, 490:124–144, 2016.

[25]
Leonard J. Schulman.
Communication on noisy channels: a coding theorem for computation.
In Proceedings., 33rd Annual Symposium on Foundations of
Computer Science, pages 724–733, 1992.

[26]
Leonard J. Schulman.
Deterministic Coding for Interactive Communication.
In Proceedings of the Twenty-Fifth Annual ACM Symposium on
Theory of Computing, STOC '93, page 747–756, New York, NY, USA, 1993.
Association for Computing Machinery.

[27]
Leonard J. Schulman.
Coding for interactive communication.
IEEE Transactions on Information Theory, 42(6):1745–1756,

[28]
Claude E. Shannon.
A mathematical theory of communication.
The Bell System Technical Journal, 27(3):379–423, 1948.