2026-07-24T10:58:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22687 2026-04-17T05:32:19Z ddc:004 open_access

Error Correction for Message Streams Gupta, Meghal Zhang, Rachel Yun error-correcting codes streaming algorithms space-efficient algorithms In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding 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 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 enc(x) of length 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 ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meghal Gupta and Rachel Yun Zhang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.59 urn:nbn:de:0030-drops-226875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59 eng https://creativecommons.org/licenses/by/4.0/legalcode