Tight Bounds for Stream Decodable Error-Correcting Codes

This motivates the notion of a stream-decodable error-correcting code. In this model, we require that the receiver can output the entire message $x_1\mathrm{\dots }{x}_n$ when any small fraction $\rho$ of the message is adversarially corrupted while using low space (for example, $\mathrm{polylog}(n)$ space) to process the transmission bit-by-bit. More formally, a stream decodable code has the following two components:

• $\mathrm{■}$

  An encoding function $\mathrm{𝖾𝗇𝖼}:{\{0,1\}}^n\to {\{0,1\}}^{m(n)}$.

• $\mathrm{■}$

  A randomized decoding algorithm $\mathrm{𝖽𝖾𝖼}:{\{0,1\}}^{m(n)}\to {\{0,1\}}^n$ that uses $s(n)$ space ($s(n)$ is much smaller than $n$: for instance, $s(n)=\mathrm{polylog}(n)$). For all $x$, and for any $z\in {\{0,1\}}^{m(n)}$ within Hamming distance $\rho \cdot m(n)$ of $\mathrm{𝖾𝗇𝖼}(x)$, it should hold that $\mathrm{𝖽𝖾𝖼}(z)$ outputs $x$ with high probability.

It is not clear that such codes should exist at all for any $s(n)=o(n)$, even for small error rates $\rho$ and an arbitrary communication blow-up $m(n)$. In particular, a standard error-correcting code could require storing the full encoding at once to process, and so it requires $s(n)=n$.

Our first result constructs stream-decodable codes that achieve the following parameters (see Theorem 1 for a precise statement).

• $\mathrm{■}$

  Error resilience of $\rho =\frac{1}{4}-\epsilon$ for any $\epsilon >0$, matching the best possible error resilience of standard error-correcting codes.

• $\mathrm{■}$

  Near-quadratic blow-up in communication: $m(n)=\frac{n^{2+r(s(n))}}{s(n)}$ (here $r(s(n))$ is small – typically $o(1)$, but when $s(n)=\log {(n)}^t$, then $r(s(n))=1/t$). This is a larger blow-up in communication than incurred by standard error-correcting codes.

The construction itself is quite simple: it encodes the message by a locally decodable code of near-linear length, and repeats the encoding $O(n)$ times. The more interesting part is the corresponding decoding algorithm for Bob. To this end, we work with stronger local decoding guarantees, specifically having access to soft information for unique decoding, and local list decoding with advice from close to $1/2$ errors.

Our next result demonstrates, surprisingly, that the communication blowup of our codes is essentially optimal: any stream-decodable code requires transmission length $m(n)=\mathrm{\Omega }\left(\frac{n^2}{s(n)}\right)$, in contrast to the standard error-correction model. (See Theorem 2 for the precise statetemt.) This result is surprising and notable because it obtains a strong lower bound on an information-theoretic quantity (the codeword blow-up) leveraging the computational restriction of space-boundedness. The lower bound is established by carefully controlling the set of message indices that the decoder can output when processing successive blocks of sub-linear size of the stream. It is also interesting to contrast this with the earlier mentioned setting of interactive communication, which despite the challenge of encoding the global conversation that is only available in local fragments, admits non-trivial schemes with a constant factor communication blow-up, from Schulman’s seminal work [26] and many follow-ups (surveyed in [10]).

Our work can be viewed as a strengthening of and resolution to most of the open problems in [12]. The problem is framed slightly differently in their work: in [12], instead of outputting $x_1\mathrm{\dots }{x}_n$, the decoder is only required to output a single bit $f(x_1\mathrm{\dots }{x}_n)$. Here, the function $f$ represents the output of an arbitrary streaming algorithm performed on $x_1\mathrm{\dots }{x}_n$, so it must be possible to compute in $s(n)$ space in a streaming manner. The function $f$ is unknown to Alice (or else she could simply send the value $f(x_1\mathrm{\dots }{x}_n)$ to Bob) but known to the adversary causing the errors. One could imagine, for example, that $f$ is an arbitrary linear function of $x_1\mathrm{\dots }{x}_n$, or one’s physical location after executing some (possibly non-commutative) sequence of movements $x_1\mathrm{\dots }{x}_n$.

For this problem, [12] provide a scheme requiring slightly larger than $O(n^4)$ encoding length. Specifically, if $s(n)=\log {(n)}^t$, their code requires $n^{4+O(1/t)}$ space. Our notion of a stream-decodable code is necessarily stronger: that is, if the decoder can write $x_1\mathrm{\dots }{x}_n$ to an output tape in that order, they can also compute the output of any streaming algorithm $f$ in low space. In this sense, we provide a generic “front-end” error-correction scheme that enables executing any streaming task in a noise-resilient manner. Further, our construction improves upon the encoding length of the one in [12], providing a nearly quadratic-length code for their problem.

Gupta and Zhang [12] also specifically investigate the scenario where Alice knows beforehand that Bob’s function $f$ is a linear function of $x_1,\mathrm{\dots },x_n$. For this restricted class of functions, they demonstrate a scheme that uses slightly larger than $O(n^2)$ encoding length.

Our final result, stated precisely as Theorem 3, is a new scheme for stream-decoding linear functions. Specifically, we improve upon Gupta and Zhang’s result, demonstrating a scheme that requires only near-linear communication in $n$ for computing linear functions. This is achieved using a tensor product of locally decodable codes for the encoding, and a careful recursive decoding approach to recover the desired linear function of the message.

Suppose otherwise; that is, suppose that there is a $(\rho ,m,s)$-coding scheme for streams, where $m=\rho n^2/{10}^{4}s$, $\rho$ is a fixed constant, and $s=s(n)\ge \log n$ (and $n$ is sufficiently large). Also, we may assume that (otherwise the statement is obvious).

We will then demonstrate how to construct an adversarial input for this coding scheme, so that $\mathrm{𝖽𝖾𝖼}$ fails with probability at least $1/2n^2$. First, note that we can assume that $\mathrm{𝖽𝖾𝖼}$ does not output anything when it receives a 0 bit (except at the end of the stream): instead, we may have $\mathrm{𝖽𝖾𝖼}$ keep track of the length of the current run of 0s (using only $O(\log n)\lesssim s$ memory), and process all the 0s when it encounters the next 1. In particular, we will have the adversary replace several parts of the input with all 0s, and thus we can assume that the algorithm does not output anything at these parts (except perhaps the last block).

For an input string $x\in {\{0,1\}}^n$, the encoding $\mathrm{𝖾𝗇𝖼}(x)$ then has length $m$. We split $\mathrm{𝖾𝗇𝖼}(x)$ up into $k=n/100s$ contiguous “blocks” which each consist of $\mathrm{\ell }=\rho n/100$ bits; denote these blocks $B_1(x),\mathrm{\dots },B_k(x)$ (we will sometimes abbreviate $B_i(x)$ by just $B_i$). We will consider what the algorithm $\mathrm{𝖽𝖾𝖼}$ may output during each block, assuming that the block $B_i$ is uncorrupted. Essentially, we will show that there is a fixed set of roughly $\mathrm{\ell }$ indices such that $\mathrm{𝖽𝖾𝖼}$ essentially only outputs indices from this set while it is processing block $i$.

To this end, we will let $a_i\in {\{0,1\}}^s$ denote the contents of the memory of $\mathrm{𝖽𝖾𝖼}$ right before receiving block $i$. Note that $a_i$ is random and may depend on the randomness of $\mathrm{𝖽𝖾𝖼}$, as well as on the bits that the adversary has changed in previous blocks. We will mostly restrict our attention to values of $a_i$ that do not cause the algorithm to fail with significant probability. Specifically, we say that $a_i$ is good with respect to $x$, or just good (for particular values of $x$ and $i$), if the probability that $\mathrm{𝖽𝖾𝖼}$ outputs an incorrect bit during block $i$ with starting memory $a_i$ is at most $1/n^2$. (This probability is taken over only the randomness of the algorithm $\mathrm{𝖽𝖾𝖼}$, since the contents of block $B_i$ are a deterministic function of $x$.)

Now, suppose that the decoder $\mathrm{𝖽𝖾𝖼}$ currently has memory state $a_i$ and is about to receive block $i$ (whose contents are $B_i$). While it processes $B_i$, it will output various bits of $x$; that is, there are various pairs $(j,b)$ for which $\mathrm{𝖽𝖾𝖼}$ will output that $x_j=b$. (We assume, as we may, that $\mathrm{𝖽𝖾𝖼}$ keeps track of which index it is on, so we can determine $j$ from the memory contents of $\mathrm{𝖽𝖾𝖼}$.) When it does so, we say that $\mathrm{𝖽𝖾𝖼}$ outputs the pair $(j,b)$. Then, let $T(a_i,B_i)$ be the set of all $(j,b)$ which $\mathrm{𝖽𝖾𝖼}$ outputs with probability at least $1/n^2$ when it receives $B_i$ with initial memory contents $a_i$. (Again, this probability is only over the randomness of $\mathrm{𝖽𝖾𝖼}$.) Note that if $a_i$ is good (with respect to $x$), then $T(a_i,B_i)$ must match $x$ (that is, $x_j=b$ for all $(j,b)\in T(a_i,B_i)$). Note that $T(a_i,B_i)$ is a deterministic function of $a_i,B_i$.

We are now ready to prove the following lemma.

Let $a_i^{(1)},\mathrm{\dots },a_i^{(r)}$ each be good $a_i$ (with respect to a particular choice of $x$ and $i$), where $r=\mathrm{\ell }/s$. Consider the following union:

Essentially, if we can show, for a particular $x$, that this union is always small, we will then be able to show that $T(a_i,B_i)$ cannot take too large a range of values as (good) $a_i$ varies, because the union of any $r$ such instances will have small size. To this end, we first show the following claim.

First observe that since each $T(a_i,B_i)$ must match $x$, this means that $𝒯$ must also match $x$ (recall that this means that for every $(j,b)\in 𝒯$, we have $x_j=b$). However, $𝒯$ is a deterministic function of $(B_i,a_i^{(1)},\mathrm{\dots },a_i^{(r)})$, which consists of $2\mathrm{\ell }$ bits. Therefore, there are only at most $2^{2\mathrm{\ell }}$ possible values that $𝒯$ can take for any particular $i$. Thus, in total (over all $i$) there are at most possible values for $𝒯$.

However, each possible value of $𝒯$ that has size at least $3\mathrm{\ell }$ can only match a $2^{-3\mathrm{\ell }}$ proportion of $x\in {\{0,1\}}^n$. Therefore, there exists some $x$ which does not match any possible $𝒯$ of size at least $3\mathrm{\ell }$, thus proving the claim. $\mathrm{⊲}$

Now fix $x$ such that Claim 12 holds, and let $i$ be arbitrary. We will now finish the proof of Lemma 11 by constructing $S_i$. Let $ℱ$ be the family that consists of $T(a_i,B_i)$ for all good $a_i$. Claim 12 means that the union of any $r$ sets in $ℱ$ has size at most $3\mathrm{\ell }$. We wish to find $S_i$ which contains all but at most $3s$ elements of each $T\in ℱ$.

Now, construct $S_i$ in steps as follows: at each step, find $T\in ℱ$ which has more than $3s$ elements which are not in $S_i$, and add all its elements to $S_i$. This process terminates when there is no such $T$ remaining. Obviously this set satisfies $|T\setminus S_i|\le 3s$ for all $T\in ℱ$, so it remains only to check that . Indeed, suppose that $|S_i|\ge 3\mathrm{\ell }$; consider the first step in which its size reached or exceeded $3\mathrm{\ell }$. Note that at each step the size of $S_i$ increases by more than $3s$, so in total the number of steps for $|S_i|$ to reach $3\mathrm{\ell }$ is at most $\frac{3\mathrm{\ell }}{3s}=r$. But then $S_i$ is the union of at most $r$ sets in $ℱ$ and has size at least $3\mathrm{\ell }$, contradicting Claim 12. Thus, $S_i$ has the desired properties, completing the proof of Lemma 11. $◀$

With this lemma proven, we return to the proof of Theorem 2. We will now demonstrate a strategy for the adversary such that, with probability at least $1/2n^2$, the decoding algorithm $\mathrm{𝖽𝖾𝖼}$ fails to output $x$. Fix the input $x$ and sets $S_i$ such that Lemma 11 is satisfied.

Now, the adversary picks a uniformly random index $j\in \{1,\mathrm{\dots },n/2\}$. Then, for each $i$ such that $S_i$ contains at least $5s(n)$ indices in $[j+10(i-1)s,j+10is)$, the adversary replaces the whole block $B_i$ with zeros (unless it is the last block). We will first show that $\mathrm{𝖽𝖾𝖼}$ must fail on this input with probability at least $1/2n^2$. Let us suppose otherwise.

As before, let $a_i$ be the (random) memory state of $\mathrm{𝖽𝖾𝖼}$ before processing $B_i$. Note that with probability at least $1/2$, all the $a_i$ are good (since in the cases where they are not, $\mathrm{𝖽𝖾𝖼}$ fails with probability at least $1/n^2$). If they are all good, then by the definition of $T$ and a union bound (over the block number $i$ and the indices $j$), with probability at least $0.99$, at every block $B_i$, the indices output during block $i$ are all in $T(a_i,B_i)$. In this case, observe that during block $i$, $\mathrm{𝖽𝖾𝖼}$ may never output the index $j+10is$ (or any greater index). Indeed, if this were not the case, during some block $\mathrm{𝖽𝖾𝖼}$ would have to output everything in $[j+10(i-1)s,j+10is)$, but then we would have $|T(a_i,B_i)\setminus S_i|>5s$, contradicting Lemma 11.

Thus, right before the last block, the algorithm cannot have output any index past $j+10ks=j+n/10$. Then, in the last block, the algorithm outputs at most $|S_i|+3s\le 3\mathrm{\ell }+3s$ by Lemma 11. Therefore, overall, with probability at least $0.49$, the algorithm outputs at most indices, and thus does not output all of $x$.

Therefore we have shown that, under this strategy for the adversary, the algorithm must fail on $x$ with probability at least $1/2n^2$. It remains only to show that the adversary deletes (i.e., replaces with $0$’s) at most an $\rho$ fraction of blocks. Indeed, it is enough to show that at most an $\rho$ fraction of blocks are deleted in expectation, since the adversary can pick $j$ such that the fewest blocks are deleted. Fix a block $B_i$. The probability that $B_i$ gets deleted is equal to the probability that $S_i$ has at least $5s$ indices in the interval $[j+10(i-1)s,j+10is)$. For any fixed $j^{\prime }\in B_i$, there are at most $10s$ choices of $j$ such that $j^{\prime }$ lands in this interval, so the probability that it does is at most $20s/n$ (since $j$ is chosen uniformly at random from $n/2$ choices). Thus the expected number of indices in $S_i$ in the interval is $(20s/n)|S_i|\le 60s\mathrm{\ell }/n$. By Markov’s inequality, the probability that this is at least $5s$ is at most . Therefore, the probability that $B_i$ is replaced with $0$’s is at most $\rho$ for each block $B_i$. The expected number of blocks replaced by $0$’s is therefore at most $\rho k$.

Putting everything together, the adversary has a strategy which deletes at most an $\rho$ fraction of blocks (and thus at most an $\rho$ fraction of the bits) which causes $\mathrm{𝖽𝖾𝖼}$ to fail with probability at least $1/2n^2$. This completes the proof of Theorem 2. $◀$