List Decoding Bounds for Binary Codes with Noiseless Feedback

Gupta, Meghal; Zhang, Rachel Yun

doi:10.4230/LIPIcs.ITCS.2025.60

List Decoding Bounds for Binary Codes with Noiseless Feedback

Meghal Gupta

University of California Berkeley, CA, USA Rachel Yun Zhang

Massachusetts Institute of Technology, Cambridge, MA, USA

Abstract

In an error-correcting code, a sender encodes a message $x\in\{0,1\}^{k}$ such that it is still decodable by a receiver on the other end of a noisy channel. In the setting of error-correcting codes with feedback, after sending each bit, the sender learns what was received at the other end and can tailor future messages accordingly.

While the unique decoding radius of feedback codes has long been known to be $\frac{1}{3}$ , the list decoding capabilities of feedback codes is not well understood. In this paper, we provide the first nontrivial bounds on the list decoding radius of feedback codes for lists of size $\ell$ . For $\ell=2$ , we fully determine the $2$ -list decoding radius to be $\frac{3}{7}$ . For larger values of $\ell$ , we show an upper bound of $\frac{1}{2}-\frac{1}{2^{\ell+2}-2}$ , and show that the same techniques for the $\ell=2$ case cannot match this upper bound in general.

Keywords and phrases:

error-correcting codes, feedback, list decoding

Funding:

Meghal Gupta: Supported by a NSF GFRP Fellowship.

Rachel Yun Zhang: Supported by NSF Graduate Research Fellowship 2141064. Supported in part by DARPA under Agreement No. HR00112020023 and by an NSF grant CNS-2154149.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Coding theory

Editors:

Raghu Meka

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Consider the problem of error-correcting codes with feedback [3]. Alice wishes to communicate a message $x\in\{0,1\}^{k}$ to Bob by transmitting a sequence of $n$ bits over a noisy channel. After sending each bit, she receives feedback through a noiseless channel, telling her what bit Bob actually received. She can use this feedback to adaptively decide her next bit of communication, potentially allowing for improvement over classical error-correcting codes. As in the classical setting, the goal is to communicate in a way such that even if some fraction $r$ of Alice’s bits are adversarially corrupted, Bob can still correctly determine $x$ .

For classical error-correcting codes without feedback, the Plotkin bound [26] states that Bob cannot uniquely decode $x$ if more than $\frac{1}{4}$ of the communication is adversarially corrupted. In other words, the unique decoding radius for binary error-correcting codes is $\frac{1}{4}$ .¹¹1In this introduction, when we state a resilience threshold/radius $r$ , we mean that for any $\epsilon>0$ there exists a protocol resilient to $r-\epsilon$ errors, with rate $O_{\epsilon}(1)$ . For sake of simplicity, we’ve omitted all $\epsilon$ ’s from this introduction. The corresponding question for codes with feedback was first posed by Berlekamp in his 1964 thesis, “Block Coding with Noiseless Feedback”: What is the maximum fraction $r$ of errors from which a feedback-based error-correcting code can still uniquely be decoded? Remarkably, he proved that in the feedback setting, the unique decoding radius increases to $\frac{1}{3}$ , surpassing the Plotkin bound.

While Berlekamp’s result tells us the unique decoding radius of feedback codes, little is known about the list-decoding case. In list-decoding, first introduced by Elias [9] and Wozencraft [34], the goal is for Bob to output a small list of messages including Alice’s. The concept of list decoding for non-feedback codes has proven to be quite illuminating for understanding the Hamming space and for various other applications (see e.g. [13] for further discussion).

In the classical setting, list decoding is useful because it can be done at a larger error radius than unique decoding. In fact, the optimal list decoding radius is known for (non-feedback) codes. For decoding into a list of size $\ell$ , the optimal radius is known to be $\frac{1}{2}-\binom{2s}{s}\cdot 2^{-2s-1}$ where $s:=\left\lfloor\frac{\ell}{2}\right\rfloor$ , which is asymptotically $\frac{1}{2}-\Theta(\ell^{-1/2})$ [5]. This is achieved by positive rate random codes.

In this paper, we investigate the analogous question for feedback codes, first posed in [30]. In a feedback code, what is the maximum fraction $r$ of adversarial errors such that Bob can always learn a list of size $\ell$ containing Alice’s message? We denote such a code as a $(\ell,r)$ -list decodable feedback code. In our work, we provide the first non-trivial unconditional lower and upper bounds for this question.

1.1 Results And Further Discussion

Our first result gives an upper bound on the error resilience (decoding radius) of an $\ell$ -list decodable feedback code.

Theorem 1.

For any positive integer $\ell$ , there is no $\left(\ell,\frac{1}{2}-\frac{1}{2^{\ell+2}-2}\right)$ -list feedback code.

Prior to this work, the only known bound on the list decoding radius of feedback codes, aside from the trivial upper bound of $\frac{1}{2}$ , was given in [30]. That result showed upper bounds for a specific subclass of feedback codes that satisfy a “generalized translation” property. It turns out this generalized translation property is not very comprehensive: we will in fact demonstrate a code that breaks the upper bound proven in [30]. In contrast, our upper bound is unconditional and applies to all feedback codes.

In the case of $\ell=1$ , Theorem 1 provides an upper bound of $\frac{1}{3}$ on the unique decoding radius, consistent with the result in [3]. The key question, however, is whether this bound is tight in general. Although we do not have an answer for arbitrary $\ell$ , we are able to show it is true in the specific case of $\ell=2$ . Specifically, we show that for any $\varepsilon>0$ , there exists a $\left(2,\frac{3}{7}-\varepsilon\right)$ -list feedback code, matching the upper bound established by Theorem 1.

Theorem 2.

For any $\varepsilon>0$ , there is a $\left(2,\frac{3}{7}-\varepsilon\right)$ -list feedback code where $n=O_{\varepsilon}(k)$ .

The particular feedback code we used to achieve $\left(2,\frac{3}{7}-\epsilon\right)$ -list decodability is the same code found in [31], which Spencer and Winkler showed achieves unique decoding up to radius $\frac{1}{3}-\epsilon$ . The code, which we’ll denote $\mathsf{SW}$ , is defined in Section 4. Compared to the $(\frac{1}{3}-\epsilon)$ -unique decodability analysis in [31], however, our analysis is significantly more involved, requiring us to characterize the likelihood of four inputs rather than one possible input at once.

A reasonable conjecture at this point is that the $\mathsf{SW}$ protocol will always give a $\left(\ell,\frac{1}{2}-\frac{1}{2^{\ell+2}-2}\right)$ -list decodable code. This would show that Theorem 1 is optimal.

Unfortunately, this turns out not to be true. We show that for $\ell=3$ , the error resilience of the Spencer-Winkler protocol does not match the upper bound given in Theorem 1. There is an adversarial corruption strategy on $\mathsf{SW}$ that requires only $\frac{31}{67}\approx 0.4627$ fraction of corruptions to confuse Bob between four different inputs, whereas the bound given by Theorem 1 is $\frac{7}{15}\approx 0.4667$ .

Theorem 3.

For any $\varepsilon>0$ , the feedback code $\mathsf{SW}$ (defined in Section 4) is not $\left(3,\frac{31}{67}+\varepsilon\right)$ -list decodable for any choice of encoding length $n=n(k)$ .

Although this result states that the $\mathsf{SW}$ feedback code is not $\left(3,\frac{7}{15}\right)$ -list decodable, it remains unknown whether a different feedback code achieves this bound or whether the upper bound can be improved.

Even the asymptotic behavior for this question remains unknown. Our upper bound suggests that the feedback list decoding radius could approach $\frac{1}{2}$ exponentially fast with respect to the list size $\ell$ . That is, the radius for $\ell$ -list decoding is given by $\frac{1}{2}-2^{-O(\ell)}$ . We conjecture that this exponential bound is in fact optimal for the feedback case and propose proving or disproving this as an interesting direction for future research.

In the case of standard ECC’s (without feedback), as mentioned earlier, the optimal list decoding radius is $\frac{1}{2}-\binom{2s}{s}\cdot 2^{-2s-1}$ for $s=\left\lfloor\frac{\ell}{2}\right\rfloor$ [5]. That is, for any $\varepsilon>0$ , there exist $\left(\ell,\frac{1}{2}-\binom{2s}{s}\cdot 2^{-2s-1}-\varepsilon\right)$ -list decodable codes. Asymptotically, this bound says that the list decoding radius is approximately $\frac{1}{2}-\Theta(\ell^{-1/2})$ , which approaches $\frac{1}{2}$ much slower than the conjectured $\frac{1}{2}-2^{-O(\ell)}$ radius for the feedback case. Even short of proving the exponential bound, demonstrating a separation between the asymptotics for the feedback and non-feedback cases would be an intriguing result.

1.2 Related Works

1.2.1 Error Correcting Codes with Feedback

We already mentioned the seminal work of [3] which introduced the concept of error-correcting codes with feedback. Berlekamp studied adversarial corruption strategies and proved that $\frac{1}{3}$ was the optimal error resilience for a feedback ECC in the face of adversarial errors. Feedback ECC’s have also been studied for the binary symmetric channel, where every bit is flipped independently with some fixed probability [4, 35].

Particularly relevant is the work of [30], who initiated the study of list decoding feedback codes and gave some preliminary bounds on the list decoding capacities and radii of codes with noiseless feedback. Using generalizations of Berlekamp’s methods, he provides upper bounds on list-decoding capacities for strategies that satisfy what he call a “generalized translation” property. By contrast, our upper bounds make no assumptions about the types of protocols allowed and are fully general.

Many other works on error-correcting codes with feedback present themselves instead under the lens of adaptive search with lies. The two setups are equivalent, and our results imply results in the field of adaptive search with lies. We discuss the relationship below.

Adaptive Search with Lies

An equivalent way of looking at error-correcting codes with unlimited feedback is as follows: After every message from Alice, Bob asks a yes or no question about Alice’s input, and Alice’s next bit is a response to that question. Then, the adversary can corrupt Alice’s responses, but only up to some fraction $\alpha$ of the time. Bob is “searching” for Alice’s input in a range $[N]$ by asking these yes/no questions, and receiving an incorrect answer up to an $\alpha$ fraction of the time. This game is known as the Rényi-Ulam game, independently introduced by Rényi in [27] and Ulam [33].

Two excellent surveys on the research in this area are presented in [8, 25]. There are a number of works that aspire to improve upon [3]. For example, [22] presents a strategy with optimal rate (asking the least possible number of questions) while still achieving the best error-correction threshold. An alternative construction meeting the same optimal error resilience was given in [31]. We mention that some works focus on a fixed (constant) number of lies rather than resilience to a fraction of errors, and ask for the smallest number of questions necessary. [24] shows the optimal bound for one lie, the original Rényi-Ulam game. Followups find the optimal strategy for two and three lies as well [20, 7].

Limited Feedback/Questions

The works of [23, 1] study the minimal number of rounds, or batches, of questions Bob needs to ask when conducting adaptive search in the Ulam-Renyi model. The work of [25] poses the open question of how many batches of feedback are necessary before the optimal strategy becomes essentially the same as the fully adaptive setting.

In a more code-centric view, this model corresponds to a feedback code with limited feedback, where Alice receives feedback only a few times throughout the protocol instead of after every bit she sends. [21] studied the case where the feedback Alice receives consists of a small fraction of Alice’s rounds. [12] took this direction even further, showing that a constant number of rounds of feedback consisting of only $\log(n)$ bits is enough to achieve the same unique decoding radius as for the unlimited feedback case. [29] showed that with $O(1)$ bits of feedback, one can achieve the zero-error capacity of the error channel with full noiseless feedback.

1.2.2 List Decoding

The notion of list decoding was introduced by Elias [9] and Wozencraft [34]. The goal is for Bob to output a small list of messages including Alice’s. Although they introduced list-decoding in the setting of random error models, the main focus since then has been for adversarial error models. See [32, 16, 14] for surveys on the topic.

One main advantage is that list decoding enables correcting up to a factor two more worst-case errors compared to unique decoding. As we stated earlier, the optimal tradeoff between the list size $\ell$ and error tolerance (in the classical non-feedback setting) is known [5]. This work shows that there are positive rate codes achieving this maximum possible error tolerance. An analogous result for $q$ -ary codes was shown in [28].

Another advantage of list-decoding is that it allows for better rate codes. One can ask what the optimal tradeoff between the error tolerance $r$ and the rate $R$ of the code is, when the list size is required to small or constant, but not necessarily achieving the optimal bounds above. In the large alphabet setting, a simple random coding argument shows that $r>1-R-o(1)$ is achievable. The work of [19] provides an explicit positive rate efficiently encodable/decodable code for this task using folded Reed Solomon codes. This research has since been expanded upon, including in [15, 6, 11, 2].

Works such as [18, 17] also discuss the tradeoff between all three parameters: list size, error tolerance, and rate.

2 Definitions

Before stating our results, let us formally define a list decodable feedback ECC.

Definition 4 ( $(\ell,r)$ -List Decodable Feedback Code).

A $(\ell,r)$ -list feedback code is a family of protocols $\{\pi_{k}\}_{k\in\mathbb{N}}$ from Alice to Bob defined as follows for each $k\in\mathbb{N}$ .

$\blacksquare$

Alice begins with an input $x\in\{0,1\}^{k}$ that she intends to communicate to Bob.
$\blacksquare$

In each of $n=n(k)=|\pi_{k}|$ rounds, Alice sends a single bit that may be flipped (by an adversary). At the end of the round, Alice learns whether the bit was flipped.
$\blacksquare$

At the end of the protocol, Bob must output a list $L$ of size $\ell$ that must contain $x$ , as long as at most $r n$ bits were flipped throughout the protocol.

The Coin Game Reformulation

Throughout the remainder of the paper, we’ll argue our results about list decodable feedback ECC’s in the language of a coin game played between two players Bob and Eve. To this end, we reformulate the task of communicating over a noisy channel with feedback as this aforementioned coin game. A version of this coin game reformulation was first given by [31] but is quite similar to the adaptive search with lies formulation of [33] and [27].

Definition 5 ( $(\ell,r;K,n)$ -Coin Game).

In the coin game parametrized by $K,n,\ell\in\mathbb{N}$ and $r\in[0,1]$ , two players Bob and Eve are playing a game on a number line. At the beginning of the game, all $K$ coins are at position $0$ . In each of $n$ rounds, Bob partitions the coins into two sets, and Eve chooses a set for which Bob moves all the coins up by $1$ .

Eve wins if, at the end of the $n$ rounds, there are $\geqslant\ell+1$ coins all with positions $\leqslant rn$ , and Bob wins otherwise.

The connection to feedback codes is as follows. The $K=2^{k}$ coins correspond to all possible values of Alice’s input. For each of the $n$ rounds of the feedback code, Bob partitions the coins into two sets based on the two possibilities $0$ and $1$ for Alice’s next message. Based on the bit that he receives, he increments the position of all coins in the opposite set; that is, the coins for which Alice would have sent the opposite bit. In this manner, at any point in time, each coin’s position is the number of corruptions that must have occurred so far if the given coin were actually Alice’s input.

Let’s say we want a scheme that is $(\ell,r)$ -list decodable. Bob wins if at the end of the $n$ rounds, there are at most $\ell$ coins left with positions $<rn$ (we say all other coins have “fallen off the board”). Eve’s goal, on the other hand, is to pick a set that Bob hears each round so that at the end of the game there are $>\ell$ coins left on the board. If she’s able to pick any sequence of sets such that $>\ell$ coins are left on the board at the end of the game, then the resulting code is necessarily not $(\ell,r)$ -list decodable, since any of the $>\ell$ coins left on the board could’ve been Alice’s input.

Notation

Let us define the notation that we will use for a coin game.

$\blacksquare$

For a coin $x$ , $\mathsf{pos}_{t}(x)$ denotes the position of coin $x$ after $t$ rounds.
$\blacksquare$

$c_{t}(i)$ denotes the coin with the $i$ ’th smallest position at $t$ rounds.
$\blacksquare$

For $i\in[K]$ , $\mathsf{posc}_{t}(i)=\mathsf{pos}_{t}(c(i))$ denotes the position of the coin with the $i$ ’th smallest position after $t$ rounds.

3 Upper Bound

In this section, we show an upper bound (impossibility result) that no $\ell$ -list feedback code can achieve an error resilience greater than $\frac{1}{2}-\frac{1}{2^{\ell+2}-2}=\frac{2^{\ell}-1}{2^{\ell+1}-1}$ . Let us state the main theorem of this section.

See 1

In the formulation of the coin game, we wish to establish that in an $n$ -round protocol with $K$ coins, the adversary can always maintain $\ell+1$ coins below position $\frac{2^{\ell}-1}{2^{\ell+1}-1}\cdot n$ for any $K$ sufficiently large compared to $\ell$ . From this, we formally conclude Theorem 1 in Section 3.3.

We begin by establishing the statement for $\ell=1$ ; that is, the adversary can always maintain $2$ coins at or below position $\frac{1}{3}\cdot n$ . This statement was known as early as [3] when the concept of feedback codes was introduced, but we recreate a proof here. Our proof for general $\ell$ is inductive and therefore requires establishing the $\ell=1$ case first.

3.1 Base Case: 1-List Feedback Codes

We want to show that the adversary can always maintain the second coin at or below position $\frac{1}{3}\cdot n$ . However, in order to use our statement as an appropriate base case for the inductive hypothesis in Section 3.2, we actually show the following stronger statement about partially completed coin games.

Consider a partially completed coin game where $m$ of the $n$ rounds have been played already. Then, the adversary can limit $\mathsf{posc}_{n}(2)$ in terms of these variables, specifically by the expression $\max\left\{\left\lceil\frac{1}{3}\cdot(n-m+\mathsf{posc}_{m}(1)+\mathsf{posc}_% {m}(2)+\mathsf{posc}_{m}(3))\right\rceil,\mathsf{pos}_{m}(2)\right\}$ . In particular, the case where $m=0$ corresponds to the situation where the entire coin game is remaining, and indeed the expression says that $\mathsf{posc}_{n}(2)$ is at most $\frac{1}{3}\cdot n$ .

Theorem 6.

For any $\varepsilon>0$ , the following holds for sufficiently large $n$ . Consider an $n$ -round coin game on $K=3$ coins in which $m$ rounds have already been completed. Then, the adversary can ensure at the end of the $n$ rounds that

\mathsf{posc}_{n}(2)\leqslant\max\left\{\left\lceil\frac{1}{3}\cdot(n-m+% \mathsf{posc}_{m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil,% \mathsf{posc}_{m}(2)\right\}.

Before proving this, let us informally describe the strategy Eve uses to achieve this bound. This strategy is essentially identical to what has appeared in previous literature such as [10]. For most of the protocol, she simply chooses the smaller (fewer elements) of the two sets given by Bob. That way, she need only move up one coin, and so on average, a coin move up by $\frac{1}{3}$ , which is what gives the $\frac{1}{3}\cdot(n-m)$ term in the stated bound. However, the issue is that the coins need not move evenly. For example, the first coin may not move at all, while the last two coins each move by $\frac{1}{2}\cdot(n-m)$ . Then, the position of the second coin increases too much, but in compensation, we have some leeway with the first coin. To use this, once the first coin is sufficiently low in position that it can never surpass the second coin, Eve switches strategies to always choosing the set that does not contain the second coin. Now, although the average coin can move up more per round, the second coin no longer moves which is what we wanted, and we do not risk the first coin catching up to the second by doing this.

Proof.

Let $\theta=\max\left\{\left\lceil\frac{1}{3}\cdot(n-m+\mathsf{posc}_{m}(1)+\mathsf% {posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil,\mathsf{posc}_{m}(2)\right\}$ . In each round $t$ , Bob chooses the set $S_{t}$ and its complement $\overline{S_{t}}$ (both subsets of the 3 coins in the game), and the adversary Eve needs to choose one set for which to move up the coins by $1$ each. Eve uses the following strategy.

For a round $t$ , while $\mathsf{posc}_{t-1}(2)<\theta$ , Eve always chooses the smaller of $S_{t}$ and $\overline{S_{t}}$ , that is the one with fewer elements. (Note that the inequality in this condition is strict, so, for example, if $\mathsf{posc}_{m}(2)\geqslant\left\lceil\frac{1}{3}\cdot(n-m+\mathsf{posc}_{m}% (1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil$ , it is possible to skip this step entirely.)

Once $\mathsf{posc}_{t}(2)$ reaches $\theta$ , then Eve instead always selects the set not containing the coin in the second position.

Let us say this transition between the two strategies occurs at round $T+1$ , so Eve spends rounds $m+1$ through $T$ inclusive doing the first strategy, and the rest of the protocol doing the second strategy. (If this round $T$ never occurs, then at the end of the protocol, $\mathsf{posc}_{n}(2)<\theta$ as we desired.) Our goal will be to show that in the remaining $n-T$ rounds, the first coin will not pass the second coin, even if it is selected to increase every time. Then there will be two coins left at the end of the protocol, both with position $\leqslant\theta$ .

Between rounds $m+1$ and $T$ , in every step, the total positions of the coins are increasing by at most $1$ . Also, the first time the inequality is violated, we must have $\mathsf{posc}_{T}(2)=\theta\geqslant\left\lceil\frac{1}{3}\cdot(n-m+\mathsf{% posc}_{m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil$ . Therefore, at the end of round $T$ , it holds that

		$\displaystyle\mathsf{posc}_{T}(1)+\mathsf{posc}_{T}(2)+\mathsf{posc}_{T}(3)% \leqslant\mathsf{posc}_{m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3)+T-m$
	$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(1)+2\mathsf{posc}_{T}(2)\leqslant\mathsf{posc}_% {m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3)+T-m$
	$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(1)-\mathsf{posc}_{T}(2)+3\cdot\left\lceil\frac{% 1}{3}\cdot(n-m+\mathsf{posc}_{m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil$
		$\displaystyle\leavevmode\nobreak\ \leqslant\mathsf{posc}_{m}(1)+\mathsf{posc}_% {m}(2)+\mathsf{posc}_{m}(3)+T-m$
	$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(1)-\mathsf{posc}_{T}(2)$
		$\displaystyle\leavevmode\nobreak\ \leqslant\mathsf{posc}_{m}(1)-\mathsf{posc}_% {m}(2)+\mathsf{posc}_{m}(3)+T-m-(n-m+\mathsf{posc}_{m}(1)+\mathsf{posc}_{m}(2)% +\mathsf{posc}_{m}(3))$
		$\displaystyle\leavevmode\nobreak\ \leqslant T-n$
	$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(2)-\mathsf{posc}_{T}(1)\geqslant n-T$

In other words, in the remaining $n-T$ rounds, the first coin will not be able to switch positions with the second or third coin. As such, $\mathsf{posc}(2)$ will never increase since it is never selected, and the first coin never surpasses it.

This concludes the proof, as it means that $\mathsf{posc}_{n}(2)$ stays at $\theta$ (or never reached $\theta$ ). $\hfill\blacktriangleleft$

3.2 Inductive Step: $\ell$ -List Feedback Codes

In this section, we establish the inductive step. We inductively show an analog of Theorem 6 for larger list sizes.

Theorem 7.

For any positive integer $\ell$ , the following holds for sufficiently large $n$ . Consider an $n$ -round coin game on $K=2^{\ell+1}-1$ coins in which $m$ rounds have already been completed. For round $m\in[n]$ , let

\theta_{\ell}:=\left\lceil\frac{1}{2^{\ell+1}-1}\cdot\left((2^{\ell}-1)\cdot(n% -m)+\mathsf{posc}_{m}(1)+\ldots+\mathsf{posc}_{m}(K)\right)\right\rceil.

If $\mathsf{posc}_{m}(1)\geqslant\theta_{\ell}+m-n$ then Eve can ensure at the end of the $n$ rounds that $\mathsf{posc}_{n}(\ell+1)\leqslant\theta_{\ell}$ .

Again, before proving this formally, let us describe Eve’s strategy at a high level. Her strategy to achieve this bound will be recursive. At the start of the protocol, she chooses the smaller of Bob’s two sets at every step, so that the average coin moves by $\frac{2^{\ell}-1}{2^{\ell+1}-1}$ , giving the $\frac{2^{\ell}-1}{2^{\ell+1}-1}\cdot(n-m)$ term in the bound. As with the $\ell=1$ case, this doesn’t give the desired bound for the final position of the $(\ell+1)$ ’th coin because it’s possible the first few coins did not move at all, while the $(\ell+1)$ ’th coin moved by more. However, it can be shown that in compensation, the position of the first coin must be very low in this case. Once the first coin is at a low enough position that even if it is selected in every remaining round, it can no longer exceed $\theta_{\ell}$ by the end of the protocol, Eve switches strategies. Now, she needs to ensure that of the remaining coins, $\ell$ of them remain below position $\theta_{\ell}$ (since we have already found one coin that will definitely remain below $\theta_{\ell}$ ). This is where her strategy becomes recursive: she simulates a new coin game on the leftmost $2^{\ell}-1$ coins of the $2^{\ell+1}-2$ remaining coins and plays on these coins according to her (recursively described) strategy for the case of $\ell-1$ .

Proof.

First we check that the statement holds for the base case $\ell=1$ . This follows from Theorem 6. In this case, we have that

	$\displaystyle\theta_{1}:=$	$\displaystyle\leavevmode\nobreak\ \left\lceil\frac{1}{3}\cdot(n-m+\mathsf{posc% }_{m}(1)+\mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))\right\rceil$
	$\displaystyle\geqslant$	$\displaystyle\leavevmode\nobreak\ \frac{1}{3}\cdot(n-m+\mathsf{posc}_{m}(1)+% \mathsf{posc}_{m}(2)+\mathsf{posc}_{m}(3))$
	$\displaystyle\geqslant$	$\displaystyle\leavevmode\nobreak\ \frac{1}{3}\cdot(\theta_{1}+2\mathsf{posc}_{% m}(2)).$

In the last step, we used the condition in the Theorem 7 that $\mathsf{posc}_{m}(1)\geqslant\theta_{\ell}+m-n$ . Rearranging, this implies that $\theta_{1}\geqslant\mathsf{posc}_{m}(2)$ . Theorem 6 states that $\mathsf{posc}_{n}(2)\leqslant\max\{\theta_{1},\mathsf{posc}_{m}(2)\}=\theta_{1}$ , since $\theta_{1}\geqslant\mathsf{posc}_{m}(2)$ , which is what we wanted to prove.

For the inductive step, let us assume the statement is true for $\ell-1$ and prove it for $\ell$ . Throughout the proof, let $\Sigma_{m}:=\mathsf{posc}_{m}(1)+\ldots+\mathsf{posc}_{m}(K)$ .

In each round $t$ , Bob’s two sets are $S_{t}$ and its complement $\overline{S_{t}}$ , and the adversary Eve needs to choose one set for which to move up the coins by $1$ each. Eve uses the following strategy.

For a round $t$ , while $\mathsf{posc}_{t-1}(1)>\theta_{\ell}+(t-1)-n$ , Eve always chooses the one of $S_{t}$ and $\overline{S_{t}}$ with fewer elements. Note that the first time it is violated, $\mathsf{posc}_{t}(1)=\theta_{\ell}+t-n$ , even if it is already violated immediately at round $t=m+1$ by the assumption. Denote the round it is first violated as $T$ if it is ever violated.

At this point (after round $T$ ) or at the start of the protocol if the condition began by being violated, it is impossible for the coin $c_{T}(1)$ to ever hit the threshold $\theta_{\ell}$ , since its position can only increase by $1$ for each of the remaining $n-T$ rounds. Thus Eve can ignore the first coin, and play a coin game on only the remaining $2^{\ell+1}-1$ coins, with the goal of keeping $\mathsf{posc}_{n}(\ell)$ below $\theta_{\ell}$ . She also opts to exclude the second half of these coins $c_{T}(2^{\ell}+1),\ldots,c_{T}(2^{\ell+1}-1)$ from her new coin game as well, and simply assumes that they will end up above the threshold. In all, the players are playing a new a coin game on $2^{\ell}-1$ coins which correspond to $c_{T}(2),\ldots,c_{T}(2^{\ell})$ , with Eve having the goal of keeping $\mathsf{posc}_{n}(\ell)$ below $\theta_{\ell}$ . She executes the strategy for this recursively, keeping $\mathsf{posc}_{n}(\ell)$ bounded by what Theorem 7 says for $\ell-1$ .

Now, let us analyze this strategy.

First, we address the case where round $T$ never occurs. In this case, at the end of the protocol, it holds that $\mathsf{posc}_{n}(1)>\theta_{\ell}-n+n=\theta_{\ell}$ . Since Eve is picking the smaller of $S_{t}$ and $\overline{S_{t}}$ each time, it holds that

		$\displaystyle\mathsf{posc}_{n}(1)+\ldots+\mathsf{posc}_{n}(2^{\ell+1}-1)% \leqslant(2^{\ell}-1)\cdot(n-m)+\Sigma_{m}$
	$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{n}(1)\leqslant\frac{1}{2^{\ell+1}-1}\cdot\left((2^% {\ell}-1)\cdot(n-m)+\Sigma_{m}\right)\leqslant\theta_{\ell},$

which is a contradiction, where the last inequality follows because the middle term is at most $\theta_{\ell}$ by definition.

Next, we address the case where round $T$ occurs at some time $m\leqslant T\leqslant n$ . After round $T$ , it holds that $\mathsf{posc}_{T}(1)=\theta_{\ell}+T-n$ exactly, and so

	$\displaystyle\mathsf{posc}_{T}(1)+\ldots+\mathsf{posc}_{T}(2^{\ell+1}-1)% \leqslant(2^{\ell}-1)\cdot(T-m)+\Sigma_{m}$
$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(2)+\ldots+\mathsf{posc}_{T}(2^{\ell+1}-1)% \leqslant(2^{\ell}-2)\cdot T-(2^{\ell}-1)\cdot m-\theta_{\ell}+n+\Sigma_{m}$
$\displaystyle\implies$	$\displaystyle\mathsf{posc}_{T}(2)+\ldots+\mathsf{posc}_{T}(2^{\ell})\leqslant(% 2^{\ell-1}-1)\cdot T-\frac{2^{\ell}-1}{2}\cdot m+\frac{1}{2}\cdot(n+\Sigma_{m}% -\theta_{\ell}).$	(1)

The coin in position $1$ at time $T$ can never fall off the board, because its position can only increment by $1$ in each of the last $T-n$ rounds, and so we can disregard it. We will now apply the inductive hypothesis to a new game played on the $2^{\ell}-1$ coins in positions $2$ through $2^{\ell}$ at time $T$ , corresponding to the coins in positions $2$ through $2^{\ell}$ at time $T$ . We will renumber the coins, so we can view this new game as being played on $2^{\ell}-1$ coins numbered $1$ through $2^{\ell}-1$ , where the position functions are given by $\mathsf{pos}^{\prime}$ and $\mathsf{posc}^{\prime}$ . Denote

\theta^{\prime}_{\ell-1}:=\left\lceil\frac{1}{2^{\ell}-1}\cdot\left((2^{\ell-1% }-1)\cdot(n-T)+\mathsf{posc}^{\prime}_{T}(1)+\ldots+\mathsf{posc}^{\prime}_{T}% (2^{\ell}-1)\right)\right\rceil.

Our goal is to show that $\theta^{\prime}_{\ell-1}\leqslant\theta_{\ell}$ . This will prove the inductive step for the following reasons:

$\blacksquare$

We have that $\mathsf{posc}^{\prime}_{T}(1)=\mathsf{posc}_{T}(2)\geqslant\mathsf{posc}_{T}(1% )=\theta_{\ell}-T+n\geqslant\theta^{\prime}_{\ell-1}-T+n$ , so the condition for the inductive step of the theorem is met.
$\blacksquare$

We know that $\mathsf{posc}_{n}(\ell+1)\leqslant\max\{\mathsf{posc}^{\prime}_{n}(\ell),% \theta_{\ell}\}$ , because coin $c_{T}(1)$ cannot surpass $\theta_{\ell}$ and all of coins $c_{T}(2)\ldots c_{T}(\ell+1)$ are at most $\mathsf{posc}^{\prime}_{n}(\ell)$ . Moreover, by the inductive hypothesis, we know that $\mathsf{posc}^{\prime}_{n}(\ell)<\theta^{\prime}_{\ell-1}\leqslant\theta_{\ell}$ , and so $\mathsf{posc}_{n}(\ell+1)\leqslant\theta_{\ell}$ as we wanted.

Now, we show the desired statement that $\theta^{\prime}_{\ell-1}\leqslant\theta_{\ell}$ . Using the bound (1) we found on $\mathsf{posc}_{T}(2)+\ldots+\mathsf{posc}_{T}(2^{\ell})=\mathsf{posc}^{\prime}% _{T}(1)+\ldots+\mathsf{posc}^{\prime}_{T}(2^{\ell}-1)$ , we have that

	$\displaystyle\theta^{\prime}_{\ell-1}$	$\displaystyle=\left\lceil\frac{1}{2^{\ell}-1}\cdot\left((2^{\ell-1}-1)\cdot(n-% T)+\mathsf{posc}^{\prime}_{T}(1)+\ldots+\mathsf{posc}^{\prime}_{T}(2^{\ell}-1)% \right)\right\rceil$
		$\displaystyle<\left\lceil\frac{1}{2^{\ell}-1}\cdot\left((2^{\ell-1}-1)\cdot(n-% T)+(2^{\ell-1}-1)\cdot T-\frac{2^{\ell}-1}{2}\cdot m+\frac{1}{2}\cdot(n+\Sigma% _{m}-\theta_{\ell})\right)\right\rceil$
		$\displaystyle=\left\lceil\frac{1}{2^{\ell+1}-2}\cdot\left((2^{\ell}-1)\cdot(n-% m)+\Sigma_{m}-\theta_{\ell}\right)\right\rceil$
		$\displaystyle\leqslant\left\lceil\frac{1}{2^{\ell+1}-2}\cdot\left(1-\frac{1}{2% ^{\ell+1}-1}\right)\left((2^{\ell}-1)\cdot(n-m)+\Sigma_{m}\right)\right\rceil$
		$\displaystyle=\left\lceil\frac{1}{2^{\ell+1}-1}\cdot\left((2^{\ell}-1)\cdot(n-% m)+\Sigma_{m}\right)\right\rceil=\theta_{\ell}.$

This concludes the inductive step of Theorem 7. $\hfill\blacktriangleleft$

3.3 Conclude Theorem 1

Finally, let us conclude Theorem 1. Let the number of coins $K$ be at least $8\cdot(2^{\ell+1}-1)$ . For Eve’s first move, have her choose the one of $S_{1}$ and $\overline{S_{1}}$ (Bob’s two provided sets) with fewer elements, so that at least half the coins remain at position $0$ . For her second move, have her choose the one of $S_{2}$ and $\overline{S_{2}}$ that keeps the most coins at $0$ , which will keep at leat $\frac{1}{4}$ of the coins at $0$ . She will do this one more time, so that after $3$ moves, there are at least $2^{\ell+1}-1$ coins at position $0$ .

Even if there are more than $2^{\ell+1}-1$ coins at position $0$ , from now, Eve will fix a subset of $2^{\ell+1}-1$ coins to play a coin game on. She wants to show that in this new $n-3$ turn coin game, she can keep $\mathsf{posc}_{n-3}(\ell+1)\leqslant\frac{2^{\ell}-1}{2^{\ell+1}-1}\cdot n$ . This follows by setting $m=0$ in Theorem 7. The theorem states that Eve can always guarantee that $\ell+1$ coins stay at or below position $\left\lceil\frac{2^{\ell}-1}{2^{\ell+1}-1}\cdot(n-3)\right\rceil\leqslant\frac% {2^{\ell}-1}{2^{\ell+1}-1}\cdot n$ . Therefore $\left(\ell+1,\frac{2^{\ell}-1}{2^{\ell+1}-1}\right)$ -list decoding is not possible.

4 Optimal 2-List Feedback Codes

In this section, we will prove that the feedback ECC from Spencer-Winkler [31] achieves $\left(2,\frac{3}{7}-\epsilon\right)$ -list decodability, matching the upper bound for $\ell=2$ given in Theorem 1.

4.1 The Spencer-Winkler Coin Game

Let us begin by defining the Spencer-Winkler strategy for the coin game.

Protocol 1 : The Spencer-Winkler ( $\mathsf{SW}$ ) Coin Game

Alice has a coin $x\in\{0,1\}^{k}$ . Bob and Eve play the coin game with $K=2^{k}$ coins. In each of $n$ rounds, Bob partitions the coins into two sets based on the parity of their positions on the board. That is, he numbers the coins from $1$ to $K$ , where $1$ is assigned to the coin with the smallest position, and $K$ is the coin that is furthest away. The odd numbered coins are in one set, and the even numbered coins are in the other. Eve chooses a set whose coins to move up by $1$ .

We will also denote by $\mathsf{SW}$ the feedback code corresponding to this family of coin game strategies. When defining a feedback code $\mathsf{SW}$ , we must also specify a choice of the code length $n(k)$ . It was shown in [31] that $\mathsf{SW}$ achieves the unique decoding bound of $\frac{1}{3}-\epsilon$ for feedback codes.

Theorem 8 ([31]).

Let $n=\frac{k}{\epsilon}$ . Then in the $\mathsf{SW}$ coin game, no matter which sets Eve chooses each round, it will hold that

\mathsf{posc}_{n}(2)>\left(\frac{1}{3}-O(\epsilon)\right)\cdot n.

Thus the $\mathsf{SW}$ coin game gives a feedback code that is uniquely decodable up to radius $\frac{1}{3}-O(\epsilon)$ .

Our goal through the rest of this section is to prove a statement about the list decodability of $\mathsf{SW}$ to list size $2$ . This proves Theorem 2.

Theorem 9.

In the $\mathsf{SW}$ coin game, no matter which sets Eve chooses each round, it holds that

\mathsf{posc}_{n}(3)>\left(\frac{3}{7}-2\epsilon\right)\cdot n.

That is, the $\mathsf{SW}$ coin game with $n=\frac{24k}{\epsilon^{3}}$ gives a feedback code that is $\left(2,\frac{2}{7}-2\epsilon\right)$ -list-decodable.

4.2 Some Useful Inequalities

Throughout this section, let $n=\frac{24k}{\epsilon^{3}}$ . Our proof that the $\mathsf{SW}$ protocol achieves $(2,\frac{3}{7})$ -list decoding follows from two inequalities, given in Lemmas 11 and 12. First, let us prove a statement about how the position of the $i$ ’th coin at each round can change.

Claim 10.

For any $t\in[n-1]$ and for any $i\in[K]$ , it holds that

\mathsf{posc}_{t+1}(i)-\mathsf{posc}_{t}(i)\in\{0,1\}.

Proof.

The $i$ ’th coin $c_{t+1}(i)$ at time $t+1$ being at position $\mathsf{posc}_{t+1}(i)$ means that at time $t$ there must’ve been $\geqslant i-1$ coins with positions $\leqslant\mathsf{posc}_{t+1}(i)$ and $\geqslant K-i$ coins with positions $\geqslant\mathsf{pos}_{t}(c_{t+1}(i))\geqslant\mathsf{posc}_{t+1}(i)-1$ . This means that the $i$ ’th coin at time $t$ must’ve had position in the range $[\mathsf{posc}_{t+1}(i)-1,\mathsf{posc}_{t+1}(i)]$ , from which the claim follows. $\hfill\vartriangleleft$

Now, we are ready to state our first key lemma, that the gaps between the positions of the first two coins must always be at least the gap between the positions of the third and fourth coins at any timestep.

Lemma 11.

At any point in the $\mathsf{SW}$ protocol, the following inequality holds:

\mathsf{posc}_{t}(2)-\mathsf{posc}_{t}(1)+1\geqslant\mathsf{posc}_{t}(4)-% \mathsf{posc}_{t}(3).

Proof.

We prove this via straightforward induction. Let us assume at time $t$ that $\mathsf{posc}_{t}(2)-\mathsf{posc}_{t}(1)+1\geqslant\mathsf{posc}_{t}(4)-% \mathsf{posc}_{t}(3)$ . This is certainly true at time $t=0$ , since all coins are at position $0$ .

By applying Claim 10, it follows that $\mathsf{posc}_{t+1}(2)-\mathsf{posc}_{t+1}(1)=\mathsf{posc}_{t}(2)-\mathsf{% posc}_{t}(1)+\{-1,0,1\}$ and similarly $\mathsf{posc}_{t+1}(4)-\mathsf{posc}_{t+1}(3)=\mathsf{posc}_{t}(4)-\mathsf{% posc}_{t}(3)+\{-1,0,1\}$ . This means that $(\mathsf{posc}(4)-\mathsf{posc}(3))-(\mathsf{posc}(2)-\mathsf{posc}(1))$ can change by at most $2$ each round, and we can focus on the relevant case that

(\mathsf{posc}_{t}(4)-\mathsf{posc}_{t}(3))-(\mathsf{posc}_{t}(2)-\mathsf{posc% }_{t}(t))\in\{0,1\}.

We split the induction into two cases. The first is if Bob moves the odd set. In this case, Bob will move up coins $c_{t}(1)$ and $c_{t}(3)$ . If $c_{t}(4)-c_{t}(3)>0$ , then this means that $c_{t}(4)-c_{t}(3)$ will decrease by $1$ , and $c_{t}(2)-c_{t}(1)$ will change by at most $1$ , so (11) will still hold at time $t+1$ . If $c_{t}(4)-c_{t}(3)=0$ , then $c_{t+1}(4)-c_{t+1}(3)\leqslant 1$ , and also by (4.2) it must be true that $\mathsf{posc}_{t}(2)-\mathsf{posc}_{t}(1)=0$ , so $c_{t+1}(2)-c_{t+1}(1)\in\{0,1\}$ as well. Therefore, $(c_{t+1}(4)-c_{t+1}(3))-(c_{t+1}(2)-c_{t+1}(1))\leqslant 1$ as desired.

The second case is if Bob moves the even set. In this case, Bob will move up coins $c_{t}(2)$ and $c_{t}(4)$ . If $\mathsf{posc}_{t}(3)-\mathsf{posc}_{t}(2)>0$ , then $c_{t}(1),c_{t}(2)$ , and $c_{t}(3)$ will still be the first, second, and third coins at time $t+1$ . Then $\mathsf{posc}_{t+1}(2)-\mathsf{posc}_{t+1}(1)=(\mathsf{posc}_{t}(2)+1)-\mathsf% {posc}_{t}(1)$ , while $\mathsf{posc}_{t+1}(4)-\mathsf{posc}_{t+1}(3)\leqslant(\mathsf{posc}_{t}(4)+1)% -\mathsf{posc}_{t}(3)$ by Claim 10, so (11) clearly follows. On the other hand, if $\mathsf{posc}_{t}(2)=\mathsf{posc}_{t}(3)$ , then moving coins the second and fourth coins at time $t$ is equivalent to moving the third and fourth coins at time $t$ , so $\mathsf{posc}_{t+1}(2)-\mathsf{posc}_{t+1}(1)=\mathsf{posc}_{t}(2)-\mathsf{% posc}_{t}(1)$ . If $\mathsf{posc}_{t}(4)>\mathsf{posc}_{t}(3)$ , then $\mathsf{posc}_{t+1}(3)=\mathsf{posc}_{t}(3)+1$ , so $\mathsf{posc}_{t+1}(4)-\mathsf{posc}_{t+1}(3)\leqslant\mathsf{posc}_{t}(4)-% \mathsf{posc}_{t}(3)$ , and (11) follows. Otherwise if $\mathsf{posc}_{t}(4)-\mathsf{posc}_{t}(3)=0$ , this means by (4.2) that $\mathsf{posc}_{t}(2)-\mathsf{posc}_{t}(1)=0$ , and since $\mathsf{posc}_{t+1}(4)=\mathsf{posc}_{t}(4)+\{0,1\}$ and $\mathsf{posc}_{t+1}(3)=\mathsf{posc}_{t}(3)+\{0,1\}$ by Claim 10, we have that $\mathsf{posc}_{t+1}(4)-\mathsf{posc}_{t+1}(3)\leqslant 1$ , so again (11) follows. $\hfill\blacktriangleleft$

The second key lemma is about the sum of the positions of the first four coins at any timestep.

Lemma 12.

At any round $0\leqslant\tau\leqslant n$ , the following holds:

\frac{1}{2}\mathsf{posc}_{\tau}(1)+\mathsf{posc}_{\tau}(2)+\mathsf{posc}_{\tau% }(3)+\mathsf{posc}_{\tau}(4)\geqslant\frac{3\tau}{2}-5\epsilon n.

Proof.

In order to analyze the positions of four coins collectively, we define a new derivative coin game that we call the quadruple coin game. The coins in this quadruple coin game are four-tuples of coins in the old game, for a total of $\binom{K}{4}$ coins in the new game. Let the set of coins in the original game be denoted $S$ , and let the set of quadruple coins be denoted $S^{\mathsf{q}}$ . The position of quadruple coin $(x_{1},x_{2},x_{3},x_{4})\in S^{\mathsf{q}}$ at time $t$ is $\frac{1}{2}\mathsf{pos}_{t}(x_{1})+\mathsf{pos}_{t}(x_{2})+\mathsf{pos}_{t}(x_% {3})+\mathsf{pos}_{t}(x_{4})$ , where here we assume that the four coins $x_{1},x_{2},x_{3},x_{4}$ are ordered according to increasing position at time $t$ .

We denote by $c^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})$ the quadruple coin $(c_{t}(i_{1}),c_{t}(i_{2}),c_{t}(i_{3}),c_{t}(i_{4}))$ , and by $\mathsf{posc}_{t}^{\mathsf{q}}(i_{1},i_{2},i_{3},i_{4})=pos_{t}^{\mathsf{q}}(c% _{t}(i_{1},i_{2},i_{3},i_{4}))$ its position at time $t$ . Our goal is to show that in this quaduple coin game, coin $c_{n}(1,2,3,4)$ will be at position $\frac{3}{2}n-4\epsilon n$ at the end of the protocol.

To do this, we will show that on average, the quadruple coins must be moving at $\approx\frac{3}{2}$ units per round, and furthermore that no coins are left behind. What we mean by the latter is that for any quadruple coin that doesn’t move enough in a given round, there is some earlier coin that is moving more than enough and compensating for the slower movement by the first coin. Precisely, we will do this via a bijection.

Let us first define $u_{t}(i)$ to be the amount that coin $c_{t}(i)$ is moved in round $t+1$ . We remark that this is not the value $\mathsf{posc}_{t+1}(i)-\mathsf{posc}_{t}(i)$ , since after round $t$ , the coins may change their orders so that $c_{t}(i)$ is no longer the $i$ ’th coin. We will also define $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})$ to be the amount that quadruple coin $c_{t}^{\mathsf{q}}(i_{1},i_{2},i_{3},i_{4})$ is moved in time $t+1$ . In general, when we write a $4$ -tuple, the four numbers should be in increasing order. We can also define the poset relation on $4$ -tuples of indices in $[K]$ by $(i_{1},i_{2},i_{3},i_{4})<(j_{1},j_{2},j_{3},j_{4})$ if $i_{\iota}\leqslant j_{\iota}$ for all $\iota\in[4]$ .

Claim 13.

At any time $t$ there is a bijection of indices $\binom{[K]}{4}\ni(i_{1},i_{2},i_{3},i_{4})\leftrightarrow(j_{1},j_{2},j_{3},j_% {4})\in\binom{[K]}{4}$ such that for any bijected values $(i_{1},i_{2},i_{3},i_{4})\leftrightarrow(j_{1},j_{2},j_{3},j_{4})$ ,

u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})+u^{\mathsf{q}}_{t}(j_{1},j_{2},j_{% 3},j_{4})\geqslant 3,

and furthermore if $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})<\frac{3}{2}$ then $(j_{1},j_{2},j_{3},j_{4})<(i_{1},i_{2},i_{3},i_{4})$ .

Proof.

We will define this bijection $\varphi_{t}$ by defining $\varphi_{t}$ on tuples $(i_{1},i_{2},i_{3},i_{4})$ for which $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})<\frac{3}{2}$ . For all other tuples that remain unbijected after this process, we can pair them up arbitrarily.

Consider a tuple $(i_{1},i_{2},i_{3},i_{4})$ for which $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})<\frac{3}{2}$ . Let’s suppose that Bob is moving the even coins in round $t+1$ (we’ll define the bijection for the odd case in the same way, except switching the words “even” and “odd” everywhere). The only way $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})$ can be less than $\frac{3}{2}$ is if there is at most one even index among the four. Let us define the map $\varphi_{t}$ depending on which of the $i_{\iota}$ is even.

\varphi_{t}(i_{1},i_{2},i_{3},i_{4})=\begin{cases}(i_{1},i_{2}-1,i_{3}-1,i_{4}% -1)&\text{$i_{1},i_{2},i_{3},i_{4}$ all odd}\\ (i_{1},i_{2},i_{3}-1,i_{4})&\text{$i_{1},i_{2},i_{3}$ odd and $i_{4}$ even}\\ (i_{1},i_{2}-1,i_{3},i_{4})&\text{$i_{1},i_{2},i_{4}$ odd and $i_{3}$ even}\\ (i_{1},i_{2},i_{3},i_{4}-1)&\text{$i_{1},i_{3},i_{4}$ odd and $i_{2}$ even}\\ (i_{1},i_{2},i_{3},i_{4}-1)&\text{$i_{2},i_{3},i_{4}$ odd and $i_{1}$ even}.% \end{cases}

It’s straightforward to check that these are all well defined, and that each of the bijected tuples contains four distinct elements. (Recall we always assume $i_{1}<i_{2}<i_{3}<i_{4}$ .)

Next, we also need to check that $\varphi_{t}(i_{1},i_{2},i_{3},i_{4})\not=\varphi_{t}(i^{\prime}_{1},i^{\prime}% _{2},i^{\prime}_{3},i^{\prime}_{4})$ for all $(i_{1},i_{2},i_{3},i_{4})\not=(i^{\prime}_{1},i^{\prime}_{2},i^{\prime}_{3},i^% {\prime}_{4})$ . To see this, we show how to invert each tuple in the image of the map $\varphi_{t}$ as we’ve defined so far. The key observation is that the five cases give five different parity tuples for the output tuple: for instance, the first case that $i_{1},i_{2},i_{3},i_{4}$ are all odd results in an output where the parities are (odd, even, even, even), whereas all the rest of the maps give outputs where two indices are odd and two are even, so we always know how to invert a tuple that is (odd, even, even, even).

\varphi_{t}^{-1}(j_{1},j_{2},j_{3},j_{4})=\begin{cases}(j_{1},j_{2}+1,j_{3}+1,% j_{4}+1)&\text{$j_{1}$ odd and $j_{2},j_{3},j_{4}$ odd}\\ (j_{1},j_{2},j_{3}+1,j_{4})&\text{$j_{1},j_{2}$ odd and $j_{3},j_{4}$ even}\\ (j_{1},j_{2}+1,j_{3},j_{4})&\text{$j_{1},j_{4}$ odd and $j_{2},j_{3}$ even}\\ (j_{1},j_{2},j_{3},j_{4}+1)&\text{$j_{1},j_{3}$ odd and $j_{2},j_{4}$ even}\\ (j_{1},j_{2},j_{3},j_{4}+1)&\text{$j_{2},j_{3}$ odd and $j_{1},j_{4}$ even}.% \end{cases}

Finally, we check that $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})+u^{\mathsf{q}}_{t}(\varphi_{t}(i_{% 1},i_{2},i_{3},i_{4}))\geqslant 3$ . In the first case that $i_{1},i_{2},i_{3},i_{4}$ are all odd and ${}^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})=0$ , $\varphi_{t}(i_{1},i_{2},i_{3},i_{4})$ has three even indices, so $u^{\mathsf{q}}_{t}(\varphi_{t}(i_{1},i_{2},i_{3},i_{4}))=3$ . In all the other cases, $(i_{1},i_{2},i_{3},i_{4})$ has one even index and $\varphi_{t}(i_{1},i_{2},i_{3},i_{4})$ has two even indices so $u^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})+u^{\mathsf{q}}_{t}(\varphi_{t}(i_{% 1},i_{2},i_{3},i_{4}))=1+2=3$ . $\hfill\vartriangleleft$

Now, let us define the potential function

\psi(t)=\sum_{(x_{1},x_{2},x_{3},x_{4})\in\binom{\{0,1\}^{k}}{4}}w_{t}(x_{1},x% _{2},x_{3},x_{4}),

where

w_{t}(x_{1},x_{2},x_{3},x_{4})=(1+\epsilon)^{\frac{1}{3}\cdot d_{t}(x_{1},x_{2% },x_{3},x_{4})}

and

d_{t}(x_{1},x_{2},x_{3},x_{4})=\max\left\{0,\frac{3t}{2}-\mathsf{pos}^{\mathsf% {q}}_{t}(x_{1},x_{2},x_{3},x_{4})\right\}.

Since $\mathsf{pos}^{\mathsf{q}}_{0}(x_{1},x_{2},x_{3},x_{4})=0$ for all $(x_{1},x_{2},x_{3},x_{4})$ at the start of the game, $\psi(0)=\binom{K}{4}$ .

Claim 14.

For any time $t$ , let us consider any bijected pair $(i_{1},i_{2},i_{3},i_{4})\leftrightarrow(j_{1},j_{2},j_{3},j_{4})$ under $\varphi_{t}$ . Define $(x_{1},x_{2},x_{3},x_{4})=c^{\mathsf{q}}_{t}(i_{1},i_{2},i_{3},i_{4})$ and $(y_{1},y_{2},y_{3},y_{4})=c^{\mathsf{q}}_{t}(j_{1},j_{2},j_{3},j_{4})$ . Then,

w_{t+1}(x_{1},x_{2},x_{3},x_{4})+w_{t+1}(y_{1},y_{2},y_{3},y_{4})\leqslant e^{% \epsilon^{2}/2}\cdot\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_{2},y_{% 3},y_{4})\right)+\epsilon,

Proof.

We proceed by casework on whether $u_{t}(x_{1},x_{2},x_{3},x_{4})$ and $u_{t}(y_{1},y_{2},y_{3},y_{4})$ are greater than or less than $\frac{3}{2}$ .

Case 1: Both $u_{t}(x_{1},x_{2},x_{3},x_{4})$ and $u_{t}(y_{1},y_{2},y_{3},y_{4})$ are at least $\frac{3}{2}$ .

In this case, $d_{t+1}(x_{1},x_{2},x_{3},x_{4})\leqslant d_{t}(x_{1},x_{2},x_{3},x_{4})$ and $d_{t+1}(y_{1},y_{2},y_{3},y_{4})\leqslant d_{t}(y_{1},y_{2},y_{3},y_{4})$ , so

$\displaystyle w_{t+1}$ $\displaystyle(x_{1},x_{2},x_{3},x_{4})+w_{t+1}(y_{1},y_{2},y_{3},y_{4})$

$\displaystyle\leqslant w_{t}(x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_{2},y_{3},% y_{4})$

$\displaystyle\leqslant e^{\epsilon^{2}/2}\cdot\left(w_{t}(x_{1},x_{2},x_{3},x_% {4})+w_{t}(y_{1},y_{2},y_{3},y_{4})\right)+\epsilon.$

Case 2: $u_{t}(x_{1},x_{2},x_{3},x_{4})<\frac{3}{2}$ .

We write $u_{t}(x_{1},x_{2},x_{3},x_{4})=\frac{3}{2}-\delta$ for some $\delta>0$ . Then $d_{t+1}(x_{1},x_{2},x_{3},x_{4})\leqslant d_{t}(x_{1},x_{2},x_{3},x_{4})+\delta$ and $u_{t}(y_{1},y_{2},y_{3},y_{4})\geqslant\frac{3}{2}-\delta$ . Let us again do casework on whether $d_{t}(y_{1},y_{2},y_{3},y_{4})$ is larger or smaller than $\delta$ .

Subcase 2.1: $d_{t}(y_{1},y_{2},y_{3},y_{4})\geqslant\delta$ .

In this case, $d_{t+1}(y_{1},y_{2},y_{3},y_{4})\leqslant d_{t}(y_{1},y_{2},y_{3},y_{4})-\delta$ . Then

	$\displaystyle w_{t+1}$	$\displaystyle(x_{1},x_{2},x_{3},x_{4})+w_{t+1}(y_{1},y_{2},y_{3},y_{4})$
		$\displaystyle\leqslant(1+\epsilon)^{\frac{1}{3}\delta}w_{t}(x_{1},x_{2},x_{3},% x_{4})+(1+\epsilon)^{-\frac{1}{3}\delta}w_{t}(y_{1},y_{2},y_{3},y_{4})$
		$\displaystyle\leqslant\frac{(1+\epsilon)^{\frac{1}{3}\delta}+(1+\epsilon)^{-% \frac{1}{3}\delta}}{2}\cdot\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_% {2},y_{3},y_{4})\right)$
		$\displaystyle\leqslant\frac{(1+\epsilon)+(1+\epsilon)^{-1}}{2}\cdot\left(w_{t}% (x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_{2},y_{3},y_{4})\right)$
		$\displaystyle\leqslant e^{\epsilon^{2}/2}\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+% w_{t}(y_{1},y_{2},y_{3},y_{4})\right)$
		$\displaystyle\leqslant e^{\epsilon^{2}/2}\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+% w_{t}(y_{1},y_{2},y_{3},y_{4})\right)+\epsilon,$

where the second inequality follows from $(j_{1},j_{2},j_{3},j_{4})<(i_{1},i_{2},i_{3},i_{4})\implies w_{t}(x_{1},x_{2},% x_{3},x_{4})\leqslant w_{t}(y_{1},y_{2},y_{3},y_{4})$ and the rearrangement inequality, and the thir inequality follows from $\frac{1}{3}\delta\leqslant\frac{1}{2}<1$ .

Subcase 2.2: $d_{t}(y_{1},y_{2},y_{3},y_{4})<\delta$ .

In this case, $d_{t+1}(y_{1},y_{2},y_{3},y_{4})=0$ , and $d_{t+1}(x_{1},x_{2},x_{3},x_{4})\leqslant d_{t}(x_{1},x_{2},x_{3},x_{4})+% \delta\leqslant d_{t}(y_{1},y_{2},y_{3},y_{4})+\delta<2\delta$ . Then

	$\displaystyle w_{t+1}$	$\displaystyle(x_{1},x_{2},x_{3},x_{4})+w_{t+1}(y_{1},y_{2},y_{3},y_{4})$
		$\displaystyle\leqslant(1+\epsilon)^{\frac{2}{3}\cdot 2\delta}+(1+\epsilon)^{0}$
		$\displaystyle\leqslant 2+\epsilon$
		$\displaystyle\leqslant\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_{2},y% _{3},y_{4})\right)+\epsilon$
		$\displaystyle\leqslant e^{\epsilon^{2}/2}\left(w_{t}(x_{1},x_{2},x_{3},x_{4})+% w_{t}(y_{1},y_{2},y_{3},y_{4})\right)+\epsilon.$

$\hfill\vartriangleleft$

Now, using Claim 14 and summing over all bijected tuples $(i_{1},i_{2},i_{3},i_{4})\leftrightarrow(j_{1},j_{2},j_{3},j_{4})$ , we get

\psi(t+1)\leqslant e^{\epsilon^{2}/2}\cdot\psi(t)+\epsilon\cdot\frac{\binom{K}% {4}}{2}.

Solving the reccurence, we get

	$\displaystyle\psi(t+1)$	$\displaystyle\leqslant e^{(t+1)\epsilon^{2}/2}\cdot\binom{K}{4}+\frac{e^{(t+1)% \epsilon^{2}/2}-1}{e^{\epsilon^{2}/2}-1}\cdot\epsilon\cdot\frac{\binom{K}{4}}{2}$
		$\displaystyle\leqslant e^{(t+1)\epsilon^{2}/2}\cdot\binom{K}{4}\cdot\left(1+% \frac{1}{2(e^{\epsilon^{2}/2}-1)}\right)$
		$\displaystyle\leqslant e^{(t+1)\epsilon^{2}/2}\cdot\binom{K}{4}\cdot\left(1+% \frac{1}{\epsilon}\right).$

Finally, we get our bound on $\frac{1}{2}\mathsf{posc}_{\tau}(1)+\mathsf{posc}_{\tau}(2)+\mathsf{posc}_{\tau% }(3)+\mathsf{posc}_{\tau}(4)$ . Let $x_{1}=c^{\mathsf{q}}_{\tau}(1)$ , $x_{2}=c^{\mathsf{q}}_{\tau}(2)$ , $x_{3}=c^{\mathsf{q}}_{\tau}(3)$ , and $x_{4}=c^{\mathsf{q}}_{\tau}(4)$ . We have that

	$\displaystyle w_{\tau}(x_{1},x_{2},x_{3},x_{4})=(1+\epsilon)^{\frac{1}{3}\cdot d% _{\tau}(x_{1},x_{2},x_{3},x_{4})}$	$\displaystyle<\psi(\tau)$
		$\displaystyle\leqslant e^{\tau\epsilon^{2}/2}\cdot\binom{K}{4}\cdot\left(1+% \frac{1}{\epsilon}\right)$
		$\displaystyle\leqslant e^{\tau\epsilon^{2}/2}\cdot K^{4}\cdot\left(1+\frac{1}{% \epsilon}\right),$

which gives

	$\displaystyle\frac{3\tau}{2}-\mathsf{pos}^{\mathsf{q}}_{\tau}(x_{1},x_{2},x_{3% },x_{4})$	$\displaystyle\leqslant d_{\tau}(x_{1},x_{2},x_{3},x_{4})$
		$\displaystyle<\frac{3}{\ln(1+\epsilon)}\cdot\left(\tau\epsilon^{2}/2+4\ln K+% \ln\left(1+\frac{1}{\epsilon}\right)\right)$
		$\displaystyle\leqslant\frac{6}{\epsilon}\cdot\left(n\epsilon^{2}/2+4\ln K+% \frac{1}{\epsilon}\right)$
		$\displaystyle\leqslant 3\epsilon n+\frac{6}{\epsilon}\cdot\left(4\ln K+\frac{1% }{\epsilon}\right)$
		$\displaystyle\leqslant 5\epsilon n,$

where we use that $\tau\leqslant n$ , $\frac{\epsilon}{2}\leqslant\ln(1+\epsilon)$ , and $\ln\left(1+\frac{1}{\epsilon}\right)\leqslant 1/\epsilon$ , and where the last inequality follows from $n=\frac{24k}{\epsilon^{3}}$ so that

\displaystyle\frac{6}{\epsilon}\cdot\left(4\ln K+\frac{1}{\epsilon}\right)% \leqslant\frac{6}{\epsilon}\left(4k+\frac{1}{\epsilon}\right)=\epsilon^{2}n+% \frac{\epsilon}{4}n<2\epsilon n.

This completes the proof of Lemma 12. $\hfill\blacktriangleleft$

4.3 The $(2,\frac{3}{7}-\epsilon)$ -List Decodability of $\mathsf{SW}$

We now return to our main goal of this section, which is to show that $\mathsf{SW}$ is $2$ -list decodable up to radius $\frac{3}{7}$ . We restate the theorem below for convenience.

See 9

Proof.

Consider the first round $n-f$ at which $\mathsf{posc}_{n-f}(4)>\left(\frac{3}{7}-2\epsilon\right)n$ . There must be such a round because $\frac{1}{2}\mathsf{posc}_{n}(1)+\mathsf{posc}_{n}(2)+\mathsf{posc}_{n}(3)+% \mathsf{posc}_{n}(4)\geqslant\frac{3}{2}n-5\epsilon n$ by Lemma 12, so $\mathsf{posc}_{n}(4)\geqslant\frac{2}{7}\cdot\left(\frac{3}{2}n-7\epsilon n% \right)=\left(\frac{3}{7}-2\epsilon\right)n$ . After round $n-f$ , there only remains $3$ relevant coins upon the board. Our goal is to show that another falls off.

Suppose that in round $n-f$ that the first coin is at position $\left(\frac{3}{7}-2\epsilon\right)n-p$ . From Lemma 11, we know that

$\displaystyle\mathsf{posc}_{n-f}(2)+\mathsf{posc}_{n-f}(3)$	$\displaystyle\geqslant\mathsf{posc}_{n-f}(1)+\mathsf{posc}_{n-f}(4)-1$
	$\displaystyle=\frac{6}{7}n-p-4\epsilon n-1$
	$\displaystyle\geqslant\frac{6}{7}n-p-5\epsilon n.$	(4)

We also know from Lemma 12 that

$\displaystyle\mathsf{posc}_{n-f}(2)+\mathsf{posc}_{n-f}(3)$	$\displaystyle\geqslant\frac{3}{2}(n-f)-5\epsilon n-\frac{1}{2}\mathsf{posc}_{n% -f}(1)-\mathsf{posc}_{n-f}(4)$
	$\displaystyle\geqslant\frac{3}{2}(n-f)-5\epsilon n-\frac{1}{2}\left(\left(% \frac{3}{7}-2\epsilon\right)n-p\right)-\left(\frac{3}{7}-2\epsilon\right)n$
	$\displaystyle=\frac{6}{7}n-\frac{3}{2}f+\frac{1}{2}p-2\epsilon n.$	(5)

Adding $\frac{1}{3}$ of Equation 4 and $\frac{2}{3}$ of Equation 5, we get

\mathsf{posc}_{n-f}(2)+\mathsf{posc}_{n-f}(3)\geqslant\frac{6}{7}n-f-3\epsilon n.

Now, suppose that the third coin does not reach position $\left(\frac{3}{7}-3\epsilon\right)n$ by the end of the game. Then, at least one of the second and third coins must move in each of the last $f$ rounds, so that $\mathsf{posc}_{t}(2)+\mathsf{posc}_{t}(3)$ increases by at least $1$ each round. This means that at round $n$ ,

	$\displaystyle\mathsf{posc}_{n}(2)+\mathsf{posc}_{n}(3)$	$\displaystyle\geqslant\mathsf{posc}_{n-f}(2)+\mathsf{posc}_{n-f}(3)+f$
		$\displaystyle\geqslant\left(\frac{6}{7}-3\epsilon\right)n,$

which gives that $\mathsf{posc}_{n}(3)\geqslant\frac{1}{2}\left(\frac{6}{7}-3\epsilon\right)n>% \left(\frac{3}{7}-2\epsilon\right)n$ , a contradiction on our assumption that the third coin never falls off the board.

Therefore, no matter which sets the adversary chooses, there will always be at most two coins left on the board at the end of the game. $\hfill\blacktriangleleft$

5 Spencer-Winkler Does Not Give $\left(3,\frac{7}{15}\right)$ -List Feedback Codes

In Section 4, we showed that the Spencer-Winkler strategy for Alice and Bob achieves a $(2,\frac{3}{7})$ -list feedback code. In this strategy, Bob always splits the sets into the even-numbered coins and the odd-numbered coins.

A reasonable conjecture might be that this strategy is always optimal, and, in fact, we do not know of any proof that it is not. However, in this section we will show that for $\ell=3$ , it does not match our upper bound of $\frac{7}{15}$ from Section 3. Whether this is because the protocol is suboptimal or because the upper bound is not tight remains open for further investigation.

See 3

As in the previous sections, we discuss the counterexample in the coin game formulation. We will show an attack for all large enough $k$ . In this setting, Bob has $K=2^{k}$ coins for some $k>1000\varepsilon^{-1}$ , and in each of $n$ rounds (Alice and Bob choose $n$ ), he partitions the coins into $2$ sets. Then, Eve chooses one of the two sets in which to move all the coins up by $1$ . Eve wins if, at the end of the protocol, at least $4$ coins remain $\lesssim\frac{31}{67}n$ .

5.1 Eve’s Strategy

We begin by stating Eve’s procedure for determining which set of coins to select at each step. For simplicity, we’ll assume that $n$ is a multiple of $67$ and write $n=67q$ . We’ll further assume $q$ is even and $\varepsilon q$ is an integer.

Protocol 2 : Eve’s Procedure

Alice has a coin $x\in\{0,1\}^{k}$ . She and Bob simulate the coin game with $K=2^{k}$ coins. For the $n$ rounds, Eve does the following:

1.

For the first $32q$ rounds, Eve selects (moves up by $1$ ) the even coins.
2.

For the next $16q$ rounds, Eve selects the odd coins.
3.

For the next $8q$ rounds, Eve selects the even coins.
4.

For the next $4q$ rounds, Eve selects the odd coins.
5.

For the next $4q$ rounds, Eve selects the even coins.
6.

For the final $3q$ rounds, Eve selects the odd coins.

5.2 Analysis of Eve’s Strategy

We will establish our main sequence of claims giving an upper bound on the positions of the first few coins after each of these steps (and a step in between as well). The claims are written out below and summarized by the following table. For each upper bound, we additionally add $+\varepsilon q$ , although we do not write it into the table for brevity.

	$\mathsf{posc}_{m}(1)$	$\mathsf{posc}_{m}(2)$	$\mathsf{posc}_{m}(3)$	$\mathsf{posc}_{m}(4)$	$\mathsf{posc}_{m}(5)$
(even) $m=32q$	0 ( $\blacktriangle$ )	16q ( $\bullet$ )	16q ( $\bullet$ )	16q ( $\bullet$ )	16q ( $\bullet$ )
(odd) $m=48q$	16q ( )	16q ( $\blacklozenge$ )	24q ( $\bullet$ )	24q ( $\bullet$ )	24q ( $\bullet$ )
(even) $m=56q$	16q ( $\blacktriangle$ )	24q ( )	24q ( $\blacklozenge$ )	28q ( $\bullet$ )	28q ( $\bullet$ )
(odd) $m=60q$	20q ( )	24q ( $\blacklozenge$ )	28q ( )	28q ( $\blacklozenge$ )	30q ( $\bullet$ )
(even) $m=62q$	20q ( $\blacktriangle$ )	26q ( )	28q ( $\blacklozenge$ )	30q ( )	30q ( $\blacklozenge$ )
(even) $m=64q$	20q ( $\blacktriangle$ )	28q ( )	28q ( $\blacklozenge$ )	31q ( $\clubsuit$ )	31q ( $\clubsuit$ )
(odd) $m=67q$	23q ( )	28q ( $\blacklozenge$ )	31q ( )	31q ( $\blacklozenge$ )	33.5q ( $\bullet$ )

Figure 3: An upper bound on the positions of the first 5 coins after

m

rounds. To each listed position bound, additionally add

+\varepsilon q

. Eve’s selection of odd or even is also noted. Symbols in the cells are referenced in the proofs below.

Establishing the bounds in the table would show that $\mathsf{posc}_{m}(4)\leqslant 31q+\varepsilon q<\left(\frac{31}{67}+% \varepsilon\right)\cdot n$ at the end of the $n$ rounds, which establishes Theorem 3.

Now, we will prove the bounds listed in the table. Each argument below will establish the bounds indicated by the corresponding symbol. Each argument requires only that the bounds in the previous line of the table hold, so we can prove the bounds in a top-down order.

To show the ( $\blacktriangle$ ) bounds, note that selecting the even coins never moves the coin in position $1$ .

Next, we establish the ( $\bullet$ ) bounds with the following claim. It shows us that for all times $m$ , for $i\leqslant 6$ we have that $\mathsf{posc}_{m}(i)<\frac{1}{2}\cdot m+\varepsilon q$

Claim 15.

For any round $m$ , as long as $k$ is sufficiently large, it holds that $\mathsf{posc}_{m}(6)<\frac{1}{2}\cdot m+\varepsilon q$ .

Proof.

Since at all steps, only the odd coins or even coins move (and there are an even number of coins total), it holds that

\mathsf{posc}_{m}(1)+\ldots+\mathsf{posc}_{m}(K)\leqslant\frac{1}{2}\cdot Km

Then,

\frac{1}{2}\cdot Km>\mathsf{posc}_{m}(6)+\ldots+\mathsf{posc}_{m}(K)\geqslant(% K-6)\cdot\mathsf{posc}_{m}(6)

which implies that

\mathsf{posc}_{m}(6)<\frac{1}{2}\cdot\frac{Km}{K-6}<\frac{1}{2}\cdot m+\varepsilon q

where the last line holds if $K=2^{k}$ is sufficiently large, for example larger than $1000\varepsilon^{-1}$ . $\hfill\vartriangleleft$

To show the ( ) bounds, note the following claim.

Claim 16.

For all $i\in[K]$ , between rounds $t$ and $t^{\prime}$ , it holds that $\mathsf{posc}_{t^{\prime}}(i)-\mathsf{posc}_{t}(i)\leqslant t^{\prime}-t$ .

Proof.

All of coins $c_{t}(1),\ldots,c_{t}(i)$ must have have position at most $\mathsf{posc}_{t}(i)$ after round $t$ . They can all move at most $t^{\prime}-t$ by round $t^{\prime}$ , so there are at least $t^{\prime}$ coins at position $\mathsf{posc}_{t}(i)+(t^{\prime}-t)$ or earlier by the end of round $t^{\prime}$ , which is what we desired. $\hfill\vartriangleleft$

Next, we establish the ( $\blacklozenge$ ) bounds with the following claim.

Claim 17.

For all coins $i\in[K-1]$ and times $t$ and $t^{\prime}$ , if the set corresponding to parity $i+1$ is not chosen in that interval, then $\mathsf{posc}_{t^{\prime}}(i+1)\leqslant\max\left\{\mathsf{posc}_{t}(i+1),% \mathsf{posc}_{t}(i)+t^{\prime}-t\right\}$ .

Proof.

Let $d:=\mathsf{posc}_{t}(i+1)-\mathsf{posc}_{t}(i)$ . For the first $d$ steps then, the coins $c_{t}(1),\ldots,c_{t}(i)$ are all necessarily before the coin $c_{t}(i+1)$ . Then, $\mathsf{posc}_{t}(i+1)$ does not increase for those $d$ rounds (if $t^{\prime}-t<d$ , then simply stop at round $t^{\prime}$ . Then, by Claim 16, in the remaining $\max\{t^{\prime}-t-d,0\}$ rounds, $\mathsf{posc}_{t}(i+1)$ increases by at most $1$ . Therefore, in total, the final position of $c_{t}(i+1)$ after round $t^{\prime}$ is $\max\{t^{\prime}-t-d+\mathsf{posc}_{t}(i+1),\mathsf{posc}_{t}(i+1)\}$ . is This gives the desired bound because $t^{\prime}-t-d+\mathsf{posc}_{t}(i+1)\leqslant t^{\prime}-t+\mathsf{posc}_{t}(% i)-\mathsf{posc}_{t}(i+1)+\mathsf{posc}_{t}(i+1)=t^{\prime}-t+\mathsf{posc}_{t% }(i)$ as desired. $\hfill\vartriangleleft$

Finally, we establish the ( $\clubsuit$ ) bounds specifically for $\mathsf{posc}_{m}(4)$ and $\mathsf{posc}_{m}(5)$ between rounds $62q$ and $64q$ .

Claim 18.

After round $m+d$ where $m=62q$ and $d$ is even and $d\leqslant 2q$ , it holds that $\mathsf{posc}_{m+d}(5)\leqslant 30q+d/2+\varepsilon q$ .

Proof.

We will show this statement inductively. This holds when $d=0$ as the base case.

Assume this is true for $d$ , and we’ll prove it for $d+2$ . By Claim 16, $\mathsf{posc}(5)$ can increase by at most $2$ in these $2$ steps, so we only have to address the case where $\mathsf{posc}_{m+d}(5)=30q+d/2+\varepsilon q$ exactly. Moreover, we must have $\mathsf{posc}_{m+d}(4)=30q+d/2+\varepsilon q$ or $\mathsf{posc}_{m+d}(4)=30q+d/2+\varepsilon q$ exactly, otherwise we would be done by Claim 17.

All the coins $c_{m}(1),c_{m}(2),c_{m}(3)$ are in position at most $28q+d+\varepsilon q<30q+d/2+\varepsilon q-10$ at the end of $d$ steps, so they cannot surpass $c_{m+d}(4)$ during these next $2$ steps.

In both the cases where $\mathsf{posc}_{m+d}(4)=30q+d/2+\varepsilon q$ and $\mathsf{posc}_{m+d}(4)=30q+d/2+\varepsilon q$ , both the 4th and 5th positions move up by exactly $1$ if the first three coins are guaranteed to be out of the picture. $\hfill\vartriangleleft$

References

[1] Rudolf Ahlswede, Ferdinando Cicalese, Christian Deppe, and Ugo Vaccaro. Two batch search with lie cost. IEEE transactions on information theory, 55(4):1433–1439, 2009. doi:10.1109/TIT.2009.2013014.
[2] Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured reed–solomon codes achieve list-decoding capacity over linear-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1458–1469, 2024. doi:10.1145/3618260.3649634.
[3] Elwyn R. Berlekamp. Block coding with noiseless feedback. PhD thesis, Massachusetts Institute of Technology, 1964.
[4] Elwyn R. Berlekamp. Block coding for the binary symmetric channel with noiseless, delayless feedback. Error-correcting Codes, pages 61–88, 1968.
[5] Volodia M Blinovskiı. Bounds for codes in decoding by a list of finite length. Problemy Peredachi Informatsii, 22(1):11–25, 1986.
[6] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic reed-solomon codes achieve list-decoding capacity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1488–1501, 2023. doi:10.1145/3564246.3585128.
[7] Christian Deppe. Solution of ulam’s searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes. Discrete Mathematics, 224(1-3):79–98, 2000. doi:10.1016/S0012-365X(00)00109-6.
[8] Christian Deppe. Coding with feedback and searching with lies. In Entropy, Search, Complexity, pages 27–70. Springer, 2007.
[9] Peter Elias. List decoding for noisy channels. Massachusetts Institute of Technology, 1957.
[10] Ran Gelles. Coding for Interactive Communication: A Survey. Foundations and Trends® in Theoretical Computer Science, 13:1–161, January 2017. doi:10.1561/0400000079.
[11] Zeyu Guo and Zihan Zhang. Randomly punctured reed-solomon codes achieve the list decoding capacity over polynomial-size alphabets. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 164–176. IEEE, 2023. doi:10.1109/FOCS57990.2023.00019.
[12] Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang. Binary error-correcting codes with minimal noiseless feedback. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1475–1487, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585126.
[13] Venkatesan Guruswami. List decoding of error correcting codes. PhD thesis, Massachusetts Institute of Technology, 2001. URL: https://api.semanticscholar.org/CorpusID:9164141.
[14] Venkatesan Guruswami. List decoding of binary codes–a brief survey of some recent results. In Coding and Cryptology: Second International Workshop, IWCC 2009, Zhangjiajie, China, June 1-5, 2009. Proceedings 2, pages 97–106. Springer, 2009. doi:10.1007/978-3-642-01877-0_10.
[15] Venkatesan Guruswami. Linear-algebraic list decoding of folded reed-solomon codes. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 77–85. IEEE, 2011. doi:10.1109/CCC.2011.22.
[16] Venkatesan Guruswami et al. Algorithmic results in list decoding. Foundations and Trends® in Theoretical Computer Science, 2(2):107–195, 2007.
[17] Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. arXiv preprint arXiv:2004.13247, 2020. arXiv:2004.13247.
[18] Venkatesan Guruswami and Srivatsan Narayanan. Combinatorial limitations of average-radius list-decoding. IEEE Transactions on Information Theory, 60(10):5827–5842, 2014. doi:10.1109/TIT.2014.2343224.
[19] Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on information theory, 54(1):135–150, 2008. doi:10.1109/TIT.2007.911222.
[20] Wojciech Guzicki. Ulam’s searching game with two lies. Journal of Combinatorial Theory, Series A, 54(1):1–19, 1990. doi:10.1016/0097-3165(90)90002-E.
[21] Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In APPROX-RANDOM, 2015.
[22] S Muthukrishnan. On optimal strategies for searching in presence of errors. In Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms, pages 680–689, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314672.
[23] Alberto Negro, Giuseppe Parlati, and P Ritrovato. Optimal adaptive search: reliable and unreliable models. In Proc. 5th Italian Conf. on Theoretical Computer Science, pages 211–231. World Scientific, 1995.
[24] Andrzej Pelc. Solution of ulam’s problem on searching with a lie. Journal of Combinatorial Theory, Series A, 44(1):129–140, 1987. doi:10.1016/0097-3165(87)90065-3.
[25] Andrzej Pelc. Searching games with errors—fifty years of coping with liars. Theoretical Computer Science, 270(1-2):71–109, 2002. doi:10.1016/S0304-3975(01)00303-6.
[26] Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445–450, 1960. doi:10.1109/TIT.1960.1057584.
[27] A. Renyi. On a problem of information theory. In MTA Mat. Kut. Int. Kozl., volume 6B, pages 505–516, 1961.
[28] Nicolas Resch, Chen Yuan, and Yihan Zhang. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. IEEE Transactions on Information Theory, 2024.
[29] Eric Ruzomberka, Yongkyu Jang, David J. Love, and H. Vincent Poor. The capacity of channels with o(1)-bit feedback. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 2768–2773, 2023. doi:10.1109/ISIT54713.2023.10206714.
[30] Ofer Shayevitz. On error correction with feedback under list decoding. In IEEE International Symposium on Information Theory, ISIT 2009, June 28 - July 3, 2009, Seoul, Korea, Proceedings, pages 1253–1257, August 2009. doi:10.1109/ISIT.2009.5205965.
[31] Joel Spencer and Peter Winkler. Three Thresholds for a Liar. Combinatorics, Probability and Computing, 1(1):81–93, 1992. doi:10.1017/S0963548300000080.
[32] Madhu Sudan. List decoding: Algorithms and applications. ACM SIGACT News, 31(1):16–27, 2000. doi:10.1145/346048.346049.
[33] Stanislaw M Ulam. Adventures of a Mathematician. Univ of California Press, 1991.
[34] John M. Wozencraft. List decoding, volume 48. Massachusetts Institute of Technology, 1958.
[35] K.Sh. Zigangirov. Number of correctable errors for transmission over a binary symmetrical channel with feedback. Problems Inform. Transmission, 12:85–97, 1976.

[bib.bib1] [1] Rudolf Ahlswede, Ferdinando Cicalese, Christian Deppe, and Ugo Vaccaro. Two batch search with lie cost. IEEE transactions on information theory, 55(4):1433–1439, 2009. doi:10.1109/TIT.2009.2013014.

[bib.bib2] [2] Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured reed–solomon codes achieve list-decoding capacity over linear-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1458–1469, 2024. doi:10.1145/3618260.3649634.

[bib.bib3] [3] Elwyn R. Berlekamp. Block coding with noiseless feedback. PhD thesis, Massachusetts Institute of Technology, 1964.

[bib.bib4] [4] Elwyn R. Berlekamp. Block coding for the binary symmetric channel with noiseless, delayless feedback. Error-correcting Codes, pages 61–88, 1968.

[bib.bib5] [5] Volodia M Blinovskiı. Bounds for codes in decoding by a list of finite length. Problemy Peredachi Informatsii, 22(1):11–25, 1986.

[bib.bib6] [6] Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic reed-solomon codes achieve list-decoding capacity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1488–1501, 2023. doi:10.1145/3564246.3585128.

[bib.bib7] [7] Christian Deppe. Solution of ulam’s searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes. Discrete Mathematics, 224(1-3):79–98, 2000. doi:10.1016/S0012-365X(00)00109-6.

[bib.bib8] [8] Christian Deppe. Coding with feedback and searching with lies. In Entropy, Search, Complexity, pages 27–70. Springer, 2007.

[bib.bib9] [9] Peter Elias. List decoding for noisy channels. Massachusetts Institute of Technology, 1957.

[bib.bib10] [10] Ran Gelles. Coding for Interactive Communication: A Survey. Foundations and Trends® in Theoretical Computer Science, 13:1–161, January 2017. doi:10.1561/0400000079.

[bib.bib11] [11] Zeyu Guo and Zihan Zhang. Randomly punctured reed-solomon codes achieve the list decoding capacity over polynomial-size alphabets. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 164–176. IEEE, 2023. doi:10.1109/FOCS57990.2023.00019.

[bib.bib12] [12] Meghal Gupta, Venkatesan Guruswami, and Rachel Yun Zhang. Binary error-correcting codes with minimal noiseless feedback. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1475–1487, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585126.

[bib.bib13] [13] Venkatesan Guruswami. List decoding of error correcting codes. PhD thesis, Massachusetts Institute of Technology, 2001. URL: https://api.semanticscholar.org/CorpusID:9164141.

[bib.bib14] [14] Venkatesan Guruswami. List decoding of binary codes–a brief survey of some recent results. In Coding and Cryptology: Second International Workshop, IWCC 2009, Zhangjiajie, China, June 1-5, 2009. Proceedings 2, pages 97–106. Springer, 2009. doi:10.1007/978-3-642-01877-0_10.

[bib.bib15] [15] Venkatesan Guruswami. Linear-algebraic list decoding of folded reed-solomon codes. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 77–85. IEEE, 2011. doi:10.1109/CCC.2011.22.

[bib.bib16] [16] Venkatesan Guruswami et al. Algorithmic results in list decoding. Foundations and Trends® in Theoretical Computer Science, 2(2):107–195, 2007.

[bib.bib17] [17] Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. arXiv preprint arXiv:2004.13247, 2020. arXiv:2004.13247.

[bib.bib18] [18] Venkatesan Guruswami and Srivatsan Narayanan. Combinatorial limitations of average-radius list-decoding. IEEE Transactions on Information Theory, 60(10):5827–5842, 2014. doi:10.1109/TIT.2014.2343224.

[bib.bib19] [19] Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on information theory, 54(1):135–150, 2008. doi:10.1109/TIT.2007.911222.

[bib.bib20] [20] Wojciech Guzicki. Ulam’s searching game with two lies. Journal of Combinatorial Theory, Series A, 54(1):1–19, 1990. doi:10.1016/0097-3165(90)90002-E.

[bib.bib21] [21] Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In APPROX-RANDOM, 2015.

[bib.bib22] [22] S Muthukrishnan. On optimal strategies for searching in presence of errors. In Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms, pages 680–689, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314672.

[bib.bib23] [23] Alberto Negro, Giuseppe Parlati, and P Ritrovato. Optimal adaptive search: reliable and unreliable models. In Proc. 5th Italian Conf. on Theoretical Computer Science, pages 211–231. World Scientific, 1995.

[bib.bib24] [24] Andrzej Pelc. Solution of ulam’s problem on searching with a lie. Journal of Combinatorial Theory, Series A, 44(1):129–140, 1987. doi:10.1016/0097-3165(87)90065-3.

[bib.bib25] [25] Andrzej Pelc. Searching games with errors—fifty years of coping with liars. Theoretical Computer Science, 270(1-2):71–109, 2002. doi:10.1016/S0304-3975(01)00303-6.

[bib.bib26] [26] Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445–450, 1960. doi:10.1109/TIT.1960.1057584.

[bib.bib27] [27] A. Renyi. On a problem of information theory. In MTA Mat. Kut. Int. Kozl., volume 6B, pages 505–516, 1961.

[bib.bib28] [28] Nicolas Resch, Chen Yuan, and Yihan Zhang. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. IEEE Transactions on Information Theory, 2024.

[bib.bib29] [29] Eric Ruzomberka, Yongkyu Jang, David J. Love, and H. Vincent Poor. The capacity of channels with o(1)-bit feedback. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 2768–2773, 2023. doi:10.1109/ISIT54713.2023.10206714.

[bib.bib30] [30] Ofer Shayevitz. On error correction with feedback under list decoding. In IEEE International Symposium on Information Theory, ISIT 2009, June 28 - July 3, 2009, Seoul, Korea, Proceedings, pages 1253–1257, August 2009. doi:10.1109/ISIT.2009.5205965.

[bib.bib31] [31] Joel Spencer and Peter Winkler. Three Thresholds for a Liar. Combinatorics, Probability and Computing, 1(1):81–93, 1992. doi:10.1017/S0963548300000080.

[bib.bib32] [32] Madhu Sudan. List decoding: Algorithms and applications. ACM SIGACT News, 31(1):16–27, 2000. doi:10.1145/346048.346049.

[bib.bib33] [33] Stanislaw M Ulam. Adventures of a Mathematician. Univ of California Press, 1991.

[bib.bib34] [34] John M. Wozencraft. List decoding, volume 48. Massachusetts Institute of Technology, 1958.

[bib.bib35] [35] K.Sh. Zigangirov. Number of correctable errors for transmission over a binary symmetrical channel with feedback. Problems Inform. Transmission, 12:85–97, 1976.

	$\displaystyle w_{t+1}$	$\displaystyle(x_{1},x_{2},x_{3},x_{4})+w_{t+1}(y_{1},y_{2},y_{3},y_{4})$
		$\displaystyle\leqslant w_{t}(x_{1},x_{2},x_{3},x_{4})+w_{t}(y_{1},y_{2},y_{3},% y_{4})$
		$\displaystyle\leqslant e^{\epsilon^{2}/2}\cdot\left(w_{t}(x_{1},x_{2},x_{3},x_% {4})+w_{t}(y_{1},y_{2},y_{3},y_{4})\right)+\epsilon.$

List Decoding Bounds for Binary Codes with Noiseless Feedback

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Results And Further Discussion

Theorem 1.

Theorem 2.

Theorem 3.

1.2 Related Works

1.2.1 Error Correcting Codes with Feedback

Adaptive Search with Lies

Limited Feedback/Questions

1.2.2 List Decoding

2 Definitions

Definition 4 ((ℓ,r)-List Decodable Feedback Code).

The Coin Game Reformulation

Definition 5 ((ℓ,r;K,n)-Coin Game).

Notation

3 Upper Bound

3.1 Base Case: 1-List Feedback Codes

Theorem 6.

Proof.

3.2 Inductive Step: ℓ-List Feedback Codes

Theorem 7.

Proof.

3.3 Conclude Theorem 1

4 Optimal 2-List Feedback Codes

4.1 The Spencer-Winkler Coin Game

Theorem 8 ([31]).

Theorem 9.

4.2 Some Useful Inequalities

Claim 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

Claim 13.

Proof.

Claim 14.

Proof.

4.3 The (𝟐,𝟑𝟕−ϵ)-List Decodability of 𝗦𝗪

Proof.

5 Spencer-Winkler Does Not Give (𝟑,𝟕𝟏𝟓)-List Feedback Codes

5.1 Eve’s Strategy

5.2 Analysis of Eve’s Strategy

Claim 15.

Proof.

Claim 16.

Proof.

Claim 17.

Proof.

Claim 18.

Proof.

References

Definition 4 ( $(\ell,r)$ -List Decodable Feedback Code).

Definition 5 ( $(\ell,r;K,n)$ -Coin Game).

3.2 Inductive Step: $\ell$ -List Feedback Codes

4.3 The $(2,\frac{3}{7}-\epsilon)$ -List Decodability of $\mathsf{SW}$

5 Spencer-Winkler Does Not Give $\left(3,\frac{7}{15}\right)$ -List Feedback Codes