Resource-competitive error correction
Varsha Dani · 2014
We present a resource-competitive Monte Carlo algorithm for the problem of error correction for message transmission along a noisy channel when a limited amount of feedback is available. To transmit a message of length n in the presence of T ≤ n/log n adversarial errors, our algorithm sends n + 2√{n(T+1)log n} +c T log n bits.