Tight bounds for stream decodable error-correcting codes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909247427575808 |
|---|---|
| author | Gupta, Meghal Guruswami, Venkatesan Singhal, Mihir |
| author_facet | Gupta, Meghal Guruswami, Venkatesan Singhal, Mihir |
| contents | In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message $x$ into a codeword. The receiver (Bob) decodes it correctly whenever there is at most a small constant fraction of adversarial error in the transmitted codeword. This work investigates the setting where Bob is computationally bounded. Specifically, Bob receives the message as a stream and must process it and write $x$ in order to a write-only tape while using low (say polylogarithmic) space. We show three basic results about this setting, which are informally as follows:
(1) There is a stream decodable code of near-quadratic length.
(2) There is no stream decodable code of sub-quadratic length.
(3) If Bob need only compute a private linear function of the input bits, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06446 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight bounds for stream decodable error-correcting codes Gupta, Meghal Guruswami, Venkatesan Singhal, Mihir Information Theory Data Structures and Algorithms In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message $x$ into a codeword. The receiver (Bob) decodes it correctly whenever there is at most a small constant fraction of adversarial error in the transmitted codeword. This work investigates the setting where Bob is computationally bounded. Specifically, Bob receives the message as a stream and must process it and write $x$ in order to a write-only tape while using low (say polylogarithmic) space. We show three basic results about this setting, which are informally as follows: (1) There is a stream decodable code of near-quadratic length. (2) There is no stream decodable code of sub-quadratic length. (3) If Bob need only compute a private linear function of the input bits, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. |
| title | Tight bounds for stream decodable error-correcting codes |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.06446 |