Error Correction for Message Streams
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918173592256512 |
|---|---|
| author | Gupta, Meghal Zhang, Rachel Yun |
| author_facet | Gupta, Meghal Zhang, Rachel Yun |
| contents | In the setting of error correcting codes, Alice wants to send a message $x \in \{0,1\}^n$ to Bob via an encoding $\text{enc}(x)$ that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice's encoding $\text{enc}(x)$ bit-by-bit and desires to compute some function $f(x)$ in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of $x$ in low space, but not compute a generic function $f$.
Our main result is an encoding and decoding procedure where 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 decoder (streaming algorithm) $A$ that on input $x$ computes $f(x)$ in space $s$, there is an explicit decoder $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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_07087 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Error Correction for Message Streams Gupta, Meghal Zhang, Rachel Yun Data Structures and Algorithms In the setting of error correcting codes, Alice wants to send a message $x \in \{0,1\}^n$ to Bob via an encoding $\text{enc}(x)$ that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice's encoding $\text{enc}(x)$ bit-by-bit and desires to compute some function $f(x)$ in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of $x$ in low space, but not compute a generic function $f$. Our main result is an encoding and decoding procedure where 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 decoder (streaming algorithm) $A$ that on input $x$ computes $f(x)$ in space $s$, there is an explicit decoder $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)$. |
| title | Error Correction for Message Streams |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2307.07087 |