Tight bounds for stream decodable error-correcting codes
<|reference_start|>Tight bounds for stream decodable error-correcting codes: 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.<|reference_end|>
@article{gupta2024tight,
    title={Tight bounds for stream decodable error-correcting codes},
    author={Meghal Gupta, Venkatesan Guruswami, and Mihir Singhal},
    journal={arXiv preprint arXiv:2407.06446},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.06446},
    primaryClass={cs.IT cs.DS math.IT}
}