2026-07-22T06:37:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23707 2025-10-27T10:42:39Z ddc:004 open_access

Tight Bounds for Stream Decodable Error-Correcting Codes Gupta, Meghal Guruswami, Venkatesan Singhal, Mihir Coding theory Streaming computation Locally decodable code Lower Bounds In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message, a bitstring x, into a codeword. The receiver (Bob) decodes x correctly whenever there is at most a small constant fraction of adversarial errors in the transmitted codeword. We investigate the setting where Bob is restricted to be a low-space streaming algorithm. 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. Note that such a primitive then allows the execution of any downstream streaming computation on x. We show three basic results about this setting, which are informally as follows: [(i)] 1) There is a stream decodable code of near-quadratic length, resilient to error-fractions approaching the optimal bound of 1/4. 2) There is no stream decodable code of sub-quadratic length, even to correct any small constant fraction of errors. 3) If Bob need only compute a private linear function of the bits of x, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. Our constructions use locally decodable codes with additional functionality in the decoding, and (for the result on linear functions) repeated tensoring. Our lower bound, which rather surprisingly demonstrates a strong information-theoretic limitation originating from a computational restriction, proceeds via careful control of the message indices that may be output during successive blocks of the stream, a task complicated by the arbitrary state of the decoder during the algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meghal Gupta and Venkatesan Guruswami and Mihir Singhal 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.13 urn:nbn:de:0030-drops-237072 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode