Round-Vs-Resilience Tradeoffs for Binary Feedback Channels

Haeupler, Kamath, and Velingker [23] considered the setting where the feedback is partial, and showed that even if Alice receives feedback bits from Bob for an arbitrarily small constant fraction of her transmissions, resilience close to (the optimal resilience of) $\frac{1}{3}$ is possible using a randomized protocol. However, the number of feedback rounds their protocol needs grows linearly with $n$, the length of Alice’s input. See [36] for a subsequent result.

Independently and concurrently to our work, [15] improved [23] and showed a deterministic protocol that uses $𝒪(\log n)$ feedback bits over $𝒪(1)$ feedback rounds to get resilience approaching $\frac{1}{3}$, along with a similar result for the erasure channel showing that the resilience approaches $1$ for this channel. The main difference between [15] and the current work is that we focus on finding the optimal resilience for any given number $r$ of feedback rounds whereas [15] focuses on showing that the resilience approaches the optimal value as the constant $r$ increases. Additionally, their work measures both the number of feedback rounds and the number of feedback bits, while we only focus on the number of rounds.

As discussed above, feedback is also known to increase the noise resilience of the adversarial binary corruption channel [4, 5], and this result played a big role in recent work in interactive coding [10, 18, 17] and two-way coding [16, 19, 11]. In interactive coding [28, 29, 30], we wish to simulate a communication protocol $\mathrm{\Pi }$ that was designed to work over the noiseless channel, by a protocol ${\mathrm{\Pi }}^{\prime }$ that works over a noisy channel. In the setting of two-way codes, like in the setting of traditional error correcting codes, Alice wishes to transmit a message $x$ to Bob over a noisy channel. However, unlike the case of traditional codes, where Alice is the only party that can transmit messages, in two-way codes Bob can also use the (noisy) channel to transmit messages back to Alice.

Observe that since Bob has no input, any two-way code can be run over the feedback channel and thus two-way error correcting codes can be viewed as protocols over a noisy feedback channel. In particular, since the noise tolerance of the binary corruption channel is only $\frac{1}{3}$, the noise resilience of binary two-way codes over the binary corruption channel is at most $\frac{1}{3}$. In the same way, results for the bounded round feedback channel give upper bounds on the noise resilience of the corresponding two-way channels.

Gupta, Kalai, and Zhang [16, 19] studied two-way error correcting codes over the binary erasure channel. Their main result is a code that is resilient to a $\frac{3}{5}$ fraction of adversarial errors, improving on the noise tolerance of the one-way binary erasure channel that is known to be $\frac{1}{2}$. We mention that the two-way coding schemes of [16, 19] exchange (almost) linear number of messages. The work of [16] also gives an upper bound of $\frac{2}{3}$ on the maximum tolerance of the two-way binary erasure channel, and an upper bound of $\frac{2}{7}$ on the maximum tolerance of the two-way binary corruption channel. Given those upper bounds, a corollary of our results is that even a single round of noiseless feedback allows for a better error tolerance than any number of noisy feedback rounds over both the erasure and corruption channels⁴⁴4To see why, observe that if Bob’s messages are noiseless, we can assume without loss of generality that Bob’s messages are much shorter, say at most an $ϵ$ fraction, of Alice’s messages. Indeed, if not, consider a modified protocol where all messages from Alice are repeated $k$ times, for some large $k$. For the erasure channel, either all the repetitions of a bit from Alice are erased or Bob knows the bit exactly. Thus, his communication does not grow with $k$. For the corruption channel, it suffices for Bob to say how many of the repetitions were received as $1$, which can be done using $\log k\ll k$ bits. Moreover, we mention that for this claim, we do not need to rely on 3, as a lower bound slightly smaller than $\frac{7}{23}$ (but greater than $\frac{2}{7}$) on the maximum error resilience of protocols with one feedback round over the binary corruption channel can be obtained unconditionally using our techniques (but is not included in the current work)..

The recent work of Efremenko, Kol, Saxena, and Zhang [11] shows that the maximum noise resilience of two-way error correcting codes for the binary corruption channel is strictly better than the noise resilience of traditional error correcting codes for this channel, which is known to be $\frac{1}{4}$ [25]. At a very high level, those results for two-way codes are obtained by implementing a (weak) feedback mechanism over channels with no built-in feedback. Related ideas were used in [10, 18, 17] to give interactive binary error correcting codes with high noise resilience.

List decodable codes were introduced in the 50’s [12, 38] and have been studied over numerous papers and found many applications since then. We next list the works most related to ours. Most of the work on list decoding was done in the asymptotic regime, where the number of codewords goes to infinity. In this work, we are interested in the optimal list decodable codes for any (potentially small) number of codewords. However, as an ingredient in our proof, we use the asymptotic results of [3] (see also [6, 21, 7]) for optimal list decoding of the corruption channel (see Lemma 11). The list decoding question was also considered for other channels, for example, over the corruption channel with feedback [32] and the erasure channel [20].

The most immediate question we leave open is proving 3 for all weighted graphs. We also propose the following potentially related conjecture, which is tight for all odd cliques with edges of equal weight.

Proving 3 would imply that our protocol in Theorem 4 has optimal noise resilience among protocols with one round of feedback over the corruption channel. Obtaining a general round-vs-resilience tradeoff for any number of feedback rounds $r$ for the corruption channel and for other well-studied channels (e.g., the binary insertion-deletion channel⁵⁵5We note that this first requires a suitable definition for the insertion-deletion channel with constant number of rounds., the binary deletion-only channel, and non-binary channels), would be interesting.

Theorem 1 considers the case of non-adaptive feedback rounds, where Alice decides ahead of time when to ask for feedback. It can be shown that the case of adaptive feedback rounds, where Alice chooses when to ask for another round of feedback after seeing the previous feedback, allows for (strictly) better round-vs-resilience tradeoffs. Our techniques can be used to write a recursive formula for the noise resilience in the adaptive case, and finding a “clean”, closed-form formula for this setting (if one exists) is left open (see Section 2.1).

The above observation implies that protocols for the erasure channel with $r$ rounds of feedback (and therefore $r+1$ messages from Alice) have the following format: Alice starts with an input $x\in {\mathrm{\Gamma }}_0={\{0,1\}}^n$. For her first message, she takes a code⁶⁶6At this point, it may be helpful to view this as a function instead of a code. We explain why we are calling it a code later. Also, a more precise way to state this would be to say that there exists an $L>0$ such that $C_0:{\mathrm{\Gamma }}_0\to {\{0,1\}}^L$, as all codewords need to be of the same length to avoid the parties from signaling through the length of the codeword. Nonetheless, we stick with statements like $C_0:{\mathrm{\Gamma }}_0\to {\{0,1\}}^{\ast }$ throughout this sketch for simplicity. $C_0:{\mathrm{\Gamma }}_0\to {\{0,1\}}^{\ast }$ and sends $C_0(x)$ to Bob. Some of the bits of $C_0(x)$ are received correctly by Bob, while the remaining bits are erased and replaced with $\perp$. Using the bits he received correctly, Bob can calculate the number of erasures ${𝖭}_1$ introduced by the channel in this round and can identify a subset ${\mathrm{\Gamma }}_1\subseteq {\mathrm{\Gamma }}_0$ of inputs for Alice that are consistent with the message he received. Note that Alice’s input $x$ must be in ${\mathrm{\Gamma }}_1$.

Then, a feedback round takes place, and as Alice learns all the received symbols, she can also compute ${𝖭}_1$ and ${\mathrm{\Gamma }}_1$. As both parties now know these values, they can now “forget” this round and “reduce”⁷⁷7We elaborate what this means exactly in the paragraph on adaptive feedback rounds below. to a smaller problem where Alice wants to transmit an element $x\in {\mathrm{\Gamma }}_1$ to Bob using a protocol with $r-1$ rounds of feedback and the maximum number of erasures the channel can insert is ${𝖭}_1$ lower than what it was before. Continuing this way, the goal of the parties is to reduce to a problem with $0$ rounds of feedback, and set of inputs ${\mathrm{\Gamma }}_r$ such that there exists a (standard) error correcting code for elements in ${\mathrm{\Gamma }}_r$ resilient to the number of erasures that the channel can insert in the last round.

It is readily seen that the protocol format described above does not care about the exact strings in the sets ${\mathrm{\Gamma }}_0,\mathrm{\dots },{\mathrm{\Gamma }}_r$, as long as their sizes stay the same. Thus, the question of whether or not the above protocol format can be instantiated to get a protocol that is resilient to $\theta$ fraction of adversarial erasures, for some $\theta \in [0,1]$, reduces to determining when to schedule the feedback rounds, and given two feedback rounds, determining the codes $C_i$ to be used by Alice between these rounds. The codes $C_i$ should be such that, given an initial set size $m=\left|{\mathrm{\Gamma }}_i\right|$ and a target set size⁸⁸8Note that $k$ is not known to the parties in advance, and thus it will be ideal if the code used is optimal for all $k$ simultaneously. $k=\left|{\mathrm{\Gamma }}_{i+1}\right|$, the number of erasures required to reduce the set size from $m$ to $k$ is the highest. Using such codes, Alice ensures that unless the adversary invests many erasures, the set of candidates shrinks substantially between feedback rounds. We first focus on designing such codes.

Codes like the above are known as list decodable codes, and have been well studied in the asymptotic regime, where $m$ tends to infinity, and exact answers are known (see, e.g., [12, 38, 6, 20, 7, 3, 32] and Lemma 11). However, for our purposes, we need the exact answer for smaller values of $m$ as well. Codes with small $m$, i.e., “small codes” or codes with few codewords, have recently received a lot of attention and have proven to be useful in designing binary protocols with high error resilience in several contexts [10, 11, 16, 18, 19]. In the current paper, we provide a complete analysis of the list-decodability of these codes for the erasure channel, giving a function $𝖽(m,k)$ that characterizes exactly the minimum amount of erasure noise needed such that for any code $C:[m]\to {\{0,1\}}^{\ast }$, one can erase $𝖽(m,k)$ fraction of the bits and ensure that Bob gets a list of candidates of length strictly smaller than $k$.

The formula for $𝖽(m,k)$ is given in Equation 7. Proving that this formula is correct requires showing both a construction (of codes with resilience approaching $𝖽(m,k)$) and an impossibility result. Our construction has the nice property that the same code is tight simultaneously for all values of $k$. Roughly speaking, our code achieves this optimal erasure noise resilience by ensuring that every coordinate is as differentiating as possible, i.e., we ensure that for all coordinates $j$, exactly $\lfloor \frac{m}{2}\rfloor$ (uniformly chosen) codewords have $0$ in that coordinate, while the remaining $\lceil \frac{m}{2}\rceil$ codewords have $1$ (see Lemmas 9 and 10). This is as opposed to randomly sampled codes where, e.g., a $\frac{1}{2^m}$ fraction (which is large for small $m$) of the coordinates are expected to be $0$ for all the codewords, and therefore not differentiate between any pair of codewords.

Even with an exact formula for $𝖽(m,k)$ in hand, it still remains to schedule the feedback round correctly in order to maximize the overall noise resilience of the obtained protocol. The fact that our constructed code is tight simultaneously for all values of $k$ is of great help for this part, as the actual value of $k$ is determined by the erasures inserted by the channel and not in our control. This means that in order to schedule the feedback rounds optimally, one needs to go over all possible values of $k$ (across all rounds) that may happen over the channel and maximize the corresponding error resilience. This requires a careful analysis of the obtained formula for $𝖽(m,k)$.

We finish this section by briefly discussing the extension of our result to adaptive feedback rounds, as hinted in Section 1.3. Recall our reduction above from $r$ to $r-1$ feedback rounds, and note that this reduction is not perfect in the following sense: the erasures inserted by the adversary in Alice’s first message in the $r$-round protocol dictate the set ${\mathrm{\Gamma }}_1$ of candidates and the budget of the $(r-1)$-round protocol. Observe that the $(r-1)$-round protocol with maximal noise resilience for transmitting a message depends on the size of the set of candidates and on the erasure budget. Now, since our $r$-round protocol is non-adaptive, meaning that the timing of all feedback rounds is fixed in advance and cannot be recalculated given the erasures in the first round, our $r$-round protocol may reduce to a sub-optimal $(r-1)$-round protocol. Therefore, when scheduling the feedback rounds for our $r$-round protocol, one needs to consider the values of $k$ that are possible across all rounds in order to get the optimal schedule.

On the other hand, if the feedback rounds can be scheduled adaptively, the reduction is indeed perfect. In this case, one just needs to schedule the first feedback round beforehand based on the possible values of $k=\left|{\mathrm{\Gamma }}_1\right|$ for this round alone, and then, upon seeing the ${𝖭}_1$ and ${\mathrm{\Gamma }}_1$ values, one can take the $(r-1)$-feedback round protocol with the maximum error resilience (when Alice’s input is from ${\mathrm{\Gamma }}_1$ and the number of erasures is ${𝖭}_1$ lower) and schedule the remaining feedback rounds according to this protocol. Thus, our techniques also lead to a tight recursive formula for the maximum error resilience in the case of adaptive feedback rounds, but converting it to a “clean” closed form formula (if at all possible) is left open.

Using this feedback, Alice’s goal in her second message is to allow Bob to uniquely identify her input. If $C:{\{0,1\}}^n\to {\{0,1\}}^{\ast }$ is the code used by Alice in her second message, the only way Bob can uniquely decode Alice’s input is if for all $y\ne y^{\prime }\in {\{0,1\}}^n$, the codewords $C(y)$ and $C(y^{\prime })$ are at least (relative) Hamming distance $\mathrm{𝖽𝖼}(y)+\mathrm{𝖽𝖼}(y^{\prime })$ apart. The reason is that if $y$ is Alice’s input, then the adversary has fractional budget $\mathrm{𝖽𝖼}(y)$ that it can use to corrupt $C(y)$, and thus the codeword received by Bob can be any string of (relative) Hamming distance at most $\mathrm{𝖽𝖼}(y)$ from $C(y)$. Similarly, if $y^{\prime }$ is Alice’s input, then the codeword received by Bob can be any string of Hamming distance at most $\mathrm{𝖽𝖼}(y^{\prime })$ from $C(y^{\prime })$. Note that the adversary cannot arrange for the received encodings to be the same if and only if $C(y)$ and $C(y^{\prime })$ are at least (relative) Hamming distance $\mathrm{𝖽𝖼}(y)+\mathrm{𝖽𝖼}(y^{\prime })$ apart. We call a code that satisfies this (relative) Hamming distance property a $\mathrm{𝖽𝖼}$-code and mention that the values $\mathrm{𝖽𝖼}(y)$ can equivalently be seen as the “distance contributed” by $y$ in such a code.

We note that unlike traditional error correcting codes that have only one distance guarantee for all pairs of codewords (i.e., the minimum distance), for $\mathrm{𝖽𝖼}$-codes, the distance between a pair of codewords may be different depending on the “compatibility” of the messages they encode. Specifically, we think of each codeword as having a different “radius” and the code needs to “pack” all the induced balls of different radii. We point out that $\mathrm{𝖽𝖼}$-codes are an example of non-equally spaced codes defined in [11].

We also observe that the small code used in our protocol for erasures can be viewed as a $\mathrm{𝖽𝖼}$-code where $\mathrm{𝖽𝖼}(y)=0$ for all inputs $y$ that Bob has ruled out (and therefore, do not need any distance guarantees), and $\mathrm{𝖽𝖼}(y)=c$ for all inputs $y$ that he has not ruled out, where $c$ is the best possible constant ($c$ is determined by the $𝖽(m,k)$ function). We mention that for the erasure channel, our protocol also needed list-decoding guarantees that are not needed here as we are only attempting to get a one feedback round protocol.

The discussion so far shows that the existence of a protocol with a given error resilience amounts to determining whether or not it holds that for all functions $\mathrm{𝖽𝖼}(\cdot )$ that can be induced by the corruptions inserted in Alice’s first message, there exists a $\mathrm{𝖽𝖼}$-code that Alice can use to compute her second message. Curiously, we show in the next subsection that this question is equivalent to our seemingly unrelated combinatorial conjecture (3) about the existence of large cuts in graphs.

The above approach of designing $\mathrm{𝖽𝖼}$-codes (that have no rounds of feedback) to construct protocols with one round of feedback can be generalized. One can similarly argue that, for any $r\ge 0$, $\mathrm{𝖽𝖼}$-codes with $r$ rounds of feedback can be used to construct protocols with $r+1$ rounds of feedback. Analogously to the above, the “extra” round is the first round, and dictates which $\mathrm{𝖽𝖼}$-code is used in the rest of the protocol. Moreover, questions about constructing $\mathrm{𝖽𝖼}$-codes with $r$ rounds of feedback can be translated to questions about graphs. The $r=0$ case is explained next, but similar ideas may be used for general $r$, with appropriate changes in the definitions of the set $P$ and $Q$ (see below).

Let $\mathrm{\Pi }$ be a protocol as above. An adversary for $\mathrm{\Pi }$ is defined by a function $\mathrm{𝖠𝖽𝗏}:{\{0,1\}}^n\to {\{0,1,\perp \}}^{L_1}\times \mathrm{\cdots }\times {\{0,1,\perp \}}^{L_{r+1}}$. For $i\in [r+1]$, we will use ${\mathrm{𝖠𝖽𝗏}}_i(\cdot )$ to denote the function that outputs the $i$-th coordinate of $\mathrm{𝖠𝖽𝗏}(\cdot )$. We next define an execution of $\mathrm{\Pi }$ in the presence of an adversary $\mathrm{𝖠𝖽𝗏}$ for $\mathrm{\Pi }$: At the beginning of the execution, Alice starts with an input $x\in {\{0,1\}}^n$. The execution consists of $r+1$ rounds and before the $i$-th round, for $i\in [r+1]$, Alice and Bob have the (same) transcript . In round $i$, Alice computes the message and sends it to Bob bit by bit, while Bob receives the string ${\tau }_i={\mathrm{𝖠𝖽𝗏}}_i(x)$. As we assume a feedback channel, if $i\le r$, Alice also receives the string ${\tau }_i$ and both the parties add ${\tau }_i$ to and continue executing the protocol.

If $i=r+1$, the execution of the protocol terminates and Bob outputs $\mathrm{𝗈𝗎𝗍}({\tau }_{\le r+1})$. Observe that this execution is completely determined by $x$, $\mathrm{\Pi }$, and $\mathrm{𝖠𝖽𝗏}$. We denote the output of $\mathrm{\Pi }$ on input $x$ in the presence of adversary $\mathrm{𝖠𝖽𝗏}$ by ${\mathrm{𝗈𝗎𝗍}}_{\mathrm{\Pi },\mathrm{𝖠𝖽𝗏}}(x)$.

Let $\mathrm{\Pi }$ be a protocol as above and $\mathrm{𝖠𝖽𝗏}$ be an adversary for $\mathrm{\Pi }$. For $x\in {\{0,1\}}^n$, the amount of noise added by $\mathrm{𝖠𝖽𝗏}$ in $\mathrm{\Pi }$ on input $x$ is the number of times Bobs’ received bit is different from the bit Alice sent. Formally, we have:

For $\theta \in [0,1]$, we say that an adversary $\mathrm{𝖠𝖽𝗏}$ has budget $\theta$ if we have

Let $\mathrm{\Pi }$ be a protocol as above and $\mathrm{𝖠𝖽𝗏}$ be an adversary for $\mathrm{\Pi }$. We say that $\mathrm{𝖠𝖽𝗏}$ is a corruption adversary if it never outputs the symbol $\perp$, i.e., for all $x\in {\{0,1\}}^n$ and all $i\in [r+1]$, we have ${\mathrm{𝖠𝖽𝗏}}_i(x)\in {\{0,1\}}^{L_i}$. We say that $\mathrm{𝖠𝖽𝗏}$ is an erasure adversary if it only “erases” the symbols sent by Alice. More precisely, we say that $\mathrm{𝖠𝖽𝗏}$ is an erasure adversary if for all $x\in {\{0,1\}}^n$, all $i\in [r+1]$, and all $j\in [L_i]$, if ${\left({\mathrm{𝖠𝖽𝗏}}_i(x)\right)}_j\ne \perp$, then we have .

Let $\mathrm{\Pi }$ be a protocol as above and $\theta \in [0,1]$. We say that $\mathrm{\Pi }$ has resilience $\theta$ over the binary erasure channel if for all erasure adversaries with budget $\theta$ and all $x\in {\{0,1\}}^n$, it holds that ${\mathrm{𝗈𝗎𝗍}}_{\mathrm{\Pi },\mathrm{𝖠𝖽𝗏}}(x)=x$. Resilience over the binary corruption channel is defined analogously.

We start by defining list decodability for erasures.

To get the intuition behind the definition of $\mathrm{𝗇𝗌}$, observe that ${\mathrm{𝗇𝗌}}_C(\mathrm{\Gamma })$ is the minimum fraction $e$ of erasures for which there exists $\tau \in {\{0,1,\perp \}}^L$ such that for all $i\in \mathrm{\Gamma }$, it is possible to erase $e\cdot L$ symbols from $C(i)$ and get $\tau$. Observe that this is equal to the fraction of coordinates where the encodings ${\left\{C(i)\right\}}_{i\in \mathrm{\Gamma }}$ are not all the same ($\mathrm{𝗇𝗌}=$ not same).

For $m,k\ge 1$, we define ${𝖽}_{\mathrm{𝖾𝗋𝖺𝗌𝖾}}(m,k)$ to be the supremum of all values $d\in [0,1]$ for which there exists $L\ge 1$ and a code $C:[m]\to {\{0,1\}}^L$ that is less-than-$k$-list decodable for erasures up to radius $d$.

Next, we define list decodability for corruptions:

Analogous to ${𝖽}_{\mathrm{𝖾𝗋𝖺𝗌𝖾}}$, for $m,k\ge 1$, we define ${𝖽}_{\mathrm{𝖼𝗈𝗋𝗋}}(m,k)$ to be the supremum of all values $d\in [0,1]$ for which there exists $L\ge 1$ and a code $C:[m]\to {\{0,1\}}^L$ that is less-than-$k$-list decodable for corruptions up to radius $d$.