Efficient Error-Correcting Codes for Sliding Windows

We consider the task of communicating an (infinite) data stream in the sliding window model, where communication takes place over a noisy channel with an adversarial substitution noise rate up to 1. Specifically, for any noise level p < 1 and any small ϵ > 0, we design an efficient coding scheme, such that as long as the effective noise level in the sliding window is below p, the receiver decodes at least a (1- p -ϵ)-prefix of the current window. We prove that it is impossible to decode more than a (1- p)-prefix of the window in the worst case, which makes our scheme optimal in this sense. Our scheme runs in polylogarithmic time in the size of the window (per transmitted element), causes constant communication overhead, and succeeds with overwhelming probability. The scheme assumes the parties preshare a long random string unknown to the channel. When the noisy channel is additive, we lift the shared randomness assumption and design a scheme that is resilient to levels of noise below p < 1/2.