Abstract
Consider the following scenario: Alice sends a message $x\in \{0,1\}^n$ to Bob, which he processes in a streaming fashion. Bob computes a sketch $f(x)$ of Alice's message while utilizing space $s\ll n$ for processing. Depending on what $f$ is, this process may be vulnerable to errors: namely, flipping a single bit of Alice’s message could corrupt Bob’s sketch. For example, if $f$ is a random linear function, even a single bit-flip has non-trivial probability of changing the sketch. In this talk, we’ll show an algorithm to make the stream error resilient. Specifically, we provide an encoding $\mathsf{enc}(x)$ that Alice can send instead of $x$, such that Bob can compute $f(x)$ even if a constant fraction of the stream is corrupted. Importantly, this scheme maintains the communication and space complexity of the original process: Alice’s encoded message is length $\text{poly}(n)$ and Bob’s sketch computation uses space $s\cdot \text{polylog}(n)$. Finally, we’ll discuss some interesting open questions in this new model.