Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-104 | 14th July 2023 05:53

A Noise Resilient Transformation for Streaming Algorithms


Authors: Meghal Gupta, Rachel Zhang
Publication: 15th July 2023 03:42
Downloads: 236


In a streaming algorithm, Bob receives an input $x \in \{0,1\}^n$ via a stream and must compute a function $f$ in low space. However, this function may be fragile to errors in the input stream. In this work, we investigate what happens when the input stream is corrupted. Our main result is an encoding of the incoming stream so that Bob is still able to compute any such function $f$ in low space when a constant fraction of the stream is corrupted.

More precisely, we describe an encoding function $\text{enc}(x)$ of length $\text{poly}(n)$ so that for any streaming algorithm $A$ that on input $x$ computes $f(x)$ in space $s$, there is an explicit streaming algorithm $B$ that computes $f(x)$ in space $s \cdot \text{polylog}(n)$ as long as there were not more than $\frac14 - \varepsilon$ fraction of (adversarial) errors in the input stream $\text{enc}(x)$.

ISSN 1433-8092 | Imprint