Interactive communication with unknown noise rate

Alice and Bob want to run a protocol over a noisy channel, where some bits are flipped adversarially. Several results show how to make an L-bit noise-free communication protocol robust over such a channel. In a recent breakthrough, Haeupler described an algorithm sending a number of bits that is conjecturally near optimal for this model. However, his algorithm critically requires prior knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge, under the additional assumption that the channel connecting Alice and Bob is private. If an adversary flips T bits, our algorithm sends L + O ( L ( T + 1 ) log ⁡ L + T ) bits in expectation and succeeds with high probability in L. It does so without any a priori knowledge of T. Assuming a lower bound conjectured by Haeupler, our result is optimal up to logarithmic factors.

Authors

• Varsha Dani
• Thomas P. Hayes
• Mahnush Movahedi
• Jared Saia
• Maxwell Young

Keywords

No keywords are indexed for this paper.