Interactive Communication with Unknown Noise Rate
Preprint
Abstract
Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring $L$ bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires $a \ priori$ knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips $T$ bits, our algorithm sends $L + O\left(\sqrt{L(T+1)\log L} + T\right)$ bits in expectation and succeeds with high probability in $L$. It does so without any $a \ priori$ knowledge of $T$. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Optimal Coding for Streaming Authentication and Interactive CommunicationIEEE Transactions on Information Theory, 2014
- Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding2014
- Error-Correcting Codes for Automatic ControlIEEE Transactions on Information Theory, 2009
- An improvement of the tree code constructionInformation Processing Letters, 2006
- Small-Bias Probability Spaces: Efficient Constructions and ApplicationsSIAM Journal on Computing, 1993
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960