Efficient Error-Correcting Codes for Sliding Windows
Ran Gelles, Rafail Ostrovsky, Alan Roytman
Abstract:
We consider that task of transmitting a data stream in the sliding window model, where communication takes place over and adversarial noisy channel with noise rate up to 1. For any noise level c < 1 we design an efficient encoding scheme, such that for any window in which the noise level does not exceed c the receiving end decodes at least a (1−c−ε)−prefix of the window, for any small ε > ο. Decoding more than(1−c)− prefix of the window is shown to be impossible in the worst case, which makes our scheme optimal in this sense. Our scheme runs in polylogarithmic time per element in the size of the window, causes constant communication overhead, and succeeds with overwhelming probability.
comment: SOFSEM 2014 PP: 258−268
Fetch PDF file of the paper
| Back to Publications List |