Error Correction for Message Streams

In the above transformation, the length of the resulting stream is $O(n^{4+\delta })$ for any $\delta >0$. In the specific case where the streaming algorithm is linear, we construct a scheme where the stream length is only quadratic, namely $O(n^{2+\delta })$. The key property of linear streaming algorithms that we will be leveraging is that they can be computed in pieces in any order, and later computations do not depend on the results of previous ones.

Note, for example, that every linear function on codomain ${\{0,1\}}^n$ admits a linear streaming algorithm. We note that linear streaming algorithms capture a large class of interesting functions, including linear sketching algorithms (see for example [12, 10, 1, 37]). For linear streaming algorithms, we show the following result.

We remark that our transformations in Theorems 1 and 3 are only for deterministic algorithms. However, this easily implies the result for algorithms $A$ that pre-sample all of their randomness (that is, algorithms that fix their randomness before receiving any bits of $x$, at which point they are deterministic for the remainder of the algorithm). Such algorithms can be viewed as sampling from a distribution over deterministic algorithms. Our transformation can then be applied to the ensuing deterministic algorithm, thus correctly computing the function $A$ with high probability while being resilient to noise.

We remark that this notion of randomized algorithms whose only access to randomness is pre-sampled at the start of computation is quite general: randomized algorithms that sample its randomness online can often be converted to protocols where the randomness is pre-sampled, see e.g. [44].

Our main theorems are stated for the setting where the input stream is binary. We remark that this assumption is without loss of generality: a larger alphabet stream can be converted to a binary one by assigning each alphabet symbol to a unique binary string.

The study of streaming algorithms began with the work Morris [42] on approximate counting; a rigorous analysis was given later in [20]. Later works introduced other classic problems in streaming, including heavy hitters [9], ${\mathrm{\ell }}_p$ approximation [2, 41, 36], and finding a nonzero entry in a vector (for turnstile algorithms) [41].

Many works, for example [22, 11, 39, 3], consider the problem of processing noisy data sets using streaming algorithms. [22] shows a memory lower bound for learning a parity function with noisy samples of random linear equations.

However, this type of noise is quite different from our treatment. In these problems, noise is inherent in the way samples are generated, whereas we are investigating noise that occurs in the communication process.

Our result can be viewed through the lens of low-space noise resilient one-way communication.

Noise resilient one-way communication, in other words, error correction [51, 35], is one of the most well-studied problems in computer science. One specific line of works related to our result is that of locally decodable codes. Locally decodable codes [52] can be viewed as a low-time and low-space version of error-correcting codes, where the goal is to learn a single bit of the original message. By constrast, for us, the decoder must be able to piece together any function of the input that is noiselessly computable in low space, with the tradeoff that the decoder accesses the entire encoding via a stream rather than via query access. Local decodable codes have been constructed in a variety of different parameter regimes, including constant query [16, 15] and near $1$ rate [38]. In our work, we will use Reed-Muller codes [43, 46] that achieve $\text{polylog}(n)$ query complexity and slightly super-linear block length.

Another line of works related to ours is that of streaming algorithms for local testing of codes [47, 40]. However, this direction was rendered moot by the recent discovery of locally testable codes with constant rate, distance, and locality [14].

The analogue of noise resilient one-way communication in the interactive setting, where Alice and Bob have inputs $x,y$ and engage in a protocol to compute some $f(x,y)$ while being resilient to error, comprises the study of coding for interactive communication. Interactive coding was studied starting with the seminal works of Schulman [48, 49, 50] and continuing in a prolific sequence of followup works, including [8, 6, 4, 5, 34, 7, 13, 25, 24, 17, 28, 26, 19, 30, 31]. We refer the reader to an excellent survey by Gelles [23] for an extensive list of related work.

The recent work of [18] studies the space complexity of interactive coding schemes. Their main result is an interactive coding scheme that preserves the space complexity of the original noiseless protocol up to a $\log (n)$ factor, where $n$ is the length of the protocol. Their result can be viewed as the interactive analogue of ours, where their noiseless and noise resilient protocols are both interactive. We remark that their techniques are quite different than ours and do not apply to our setting, however, since their approach crucially relies on the communication of feedback from Bob to Alice.

Let $z$ be the incoming stream that Bob receives. At a high level, the algorithm $B_A$ runs by generating many guesses for $A(x)$ along with confidences indicating how likely that guess was correct (depending on how much error is witnessed while generating the guess). At the end, the guess that has the most cumulative confidence is outputted.

For $i,j$ where $j-i$ is an integer power of $r$, we define the algorithm $\mathrm{𝖾𝗌𝗍𝖠}(i,j)$ that takes in two input two indices $i,j\in [n]$. It reads $N_{j-i}$ many bits of $z$ after which it outputs a guess for $A_{i,j}(x)$ along with a confidence. In particular, $\mathrm{𝖾𝗌𝗍𝖠}(0,n)$ outputs a guess for $A(x)$ along with a confidence. By running $\mathrm{𝖾𝗌𝗍𝖠}(0,n)$ many times and aggregating the guesses weighted by the confidences, we obtain a final output.

To compute $\mathrm{𝖾𝗌𝗍𝖠}(i,j)$, we break down the interval $(i:j]$ into $r$ subintervals $(i_0:i_1],(i_1:i_2],\mathrm{\dots },(i_{r-1}:i_r]$ where $i_a=i+a\cdot \frac{j-i}{r}$. We then recursively formulate guesses for each $A\left(x(i_{a-1}:i_a]\right)$ over many iterations by calling $\mathrm{𝖾𝗌𝗍𝖠}(i_{a-1},i_{a)}$ each many times. The choice of $a$ in each iteration must be randomized, so that the adversary cannot attack any single choice of $a$. More specifically, we will split up the $N_{j-i}$ length input stream into $\mathrm{\ell }$ chunks, each of length $N_{j-i}/\mathrm{\ell }$ bits. Each chunk is split into $r$ sections, each of size $N_{j-i}/(\mathrm{\ell }\cdot r)=N_{(j-i)/r}$. In each chunk, we pick a random permutation $({\pi }_1,{\pi }_2,\mathrm{\dots },{\pi }_r)$ of $[r]$. In the $a$’th section of the chunk, we will compute on the subproblem corresponding to interval $\left(i_{{\pi }_a-1}:i_{{\pi }_a}\right]$ by calling $\mathrm{𝖾𝗌𝗍𝖠}(i_{{\pi }_a-1},i_{{\pi }_a})$.

Whenever a recursive call to $\mathrm{𝖾𝗌𝗍𝖠}(i_{a-1},i_a)$ is completed, outputting $(\widehat{q},\widehat{c})$, then: if $q_a=\widehat{q}$ then the confidence $c_a$ is increased by $\widehat{c}$, and if $q_a\ne \widehat{q}$ then the confidence $c_a$ is decreased by $\widehat{c}$. If the confidence $c_a$ becomes negative, then we are more sure that the correct state is $\widehat{q}$ rather than $q_a$: then $q_a$ is replaced by $\widehat{q}$ and the confidence is negated (so that it’s positive).

Let $z$ be the incoming stream that Bob receives. At a high level, the algorithm $B_A$ runs by generating many guesses for $A(x)$ along with confidences indicating how likely that guess was correct (depending on how much error is witnessed while generating the guess). At the end, the guess that has the most cumulative confidence is outputted.

For $i,j$ where $j-i$ is an integer power of $r$, we define the algorithm $\mathrm{𝖾𝗌𝗍𝖠}(i,j,q)$ that has the following syntax:

• $\mathrm{■}$

  $\mathrm{𝖾𝗌𝗍𝖠}(i,j,q)$ takes as input two indices $i,j\in [n]$ along with a state $q\in {\{0,1\}}^s$ which represents a guess for the state of $A(q,x(i:j])$.

• $\mathrm{■}$

  It reads $N_{j-i}:={(r\cdot \mathrm{\ell })}^{{\log }_r(j-i)}\cdot N(n)$ many bits of $z$ after which it outputs a guess for $A(q,x(i:j])$ along with a confidence.

In particular, $\mathrm{𝖾𝗌𝗍𝖠}(0,n,q)$ outputs a guess for $A(x)$ along with a confidence. By running $\mathrm{𝖾𝗌𝗍𝖠}(0,n,q)$ many times and aggregating the guesses weighted by the confidences, we obtain a final output.

At a high level, to compute $\mathrm{𝖾𝗌𝗍𝖠}(i,j,q)$, we break down the interval $(i:j]$ into $r$ subintervals $(i_0:i_1],(i_1:i_2],\mathrm{\dots },(i_{r-1}:i_r]$ where $i_a=i+a\cdot \frac{j-i}{r}$. We then recursively formulate guesses for each $A\left(x(1:i_a]\right)$ over many iterations by calling $\mathrm{𝖾𝗌𝗍𝖠}(i_{a-1},i_a,q_{a-1})$ for some state $q_{a-1}$. The choice of $a$ in each iteration must be randomized, so that the adversary cannot attack any single choice of $a$. More specifically, we will split up the $N_{j-i}$ length input stream into $\mathrm{\ell }$ chunks, each of length $N_{j-i}/\mathrm{\ell }$ bits. Each chunk is split into $r$ sections, each of size $N_{j-i}/(\mathrm{\ell }\cdot r)=N_{(j-i)/r}$. In each chunk, we pick a random permutation $({\pi }_1,{\pi }_2,\mathrm{\dots },{\pi }_r)$ of $[r]$. In the $a$’th section of the chunk, we will compute on the subproblem corresponding to interval $\left(i_{{\pi }_a-1}:i_{{\pi }_a}\right]$ by calling $\mathrm{𝖾𝗌𝗍𝖠}(i_{{\pi }_a-1},i_{{\pi }_a},q_{{\pi }_a-1})$.

Note that as the algorithm $A$ is computed sequentially, computing a guess for $A\left(x[1:i_a]\right)$ requires having a starting state $q_{a-1}$ for $A\left(x[1:i_{a-1}]\right)$. Thus, throughout the entire computation, we will keep track of the best guess and associated confidence for each of the $r$ states $A\left(x[1:i_a]\right)$, denoted $(q_a,c_a)$ and all initialized to $(\mathrm{\varnothing },0)$.

These pairs $(q_a,c_a)$ are maintained as follows. Whenever a recursive call to $\mathrm{𝖾𝗌𝗍𝖠}(i_{a-1},i_a,q_{a-1})$ is completed, outputting $(\widehat{q},\widehat{c})$, then: if $q_a=\widehat{q}$ then the confidence $c_a$ is increased by $\widehat{c}$, and if $q_a\ne \widehat{q}$ then the confidence $c_a$ is decreased by $\widehat{c}$. If the confidence $c_a$ becomes negative, then we are more sure that the correct state is $\widehat{q}$ rather than $q_a$: then $q_a$ is replaced by $\widehat{q}$ and the confidence is negated (so that it’s positive). In this last case where $q_a$ is replaced, we have no more reason to believe that further computations of $q_{a^{\prime }}$, $a^{\prime }>a$, are correct since they all depended on $q_a$, so we erase all such pairs $(q_{a^{\prime }},c_{a^{\prime }})$ and reset them to $(\mathrm{\varnothing },0)$. A key point in our analysis is to understand why this does not cause the error probability to accumulate.