Interactive Communication Over a Noisy Channel

Alice and Bob want to hold a conversation over a noisy channel on which adversarially chosen bits may be flipped. How can they communicate robustly despite such an attack?

When the conversation is one-way, i.e. Alice wants to send Bob a single message, this is a well studied problem, solved by error-correcting codes. However, these codes are not useful, for instance, when Alice and Bob need to take turns sending single bits.  To solve this problem, Schulman (1992) invented tree codes, showing that for sufficiently small noise rates the conversation can be robustly simulated using a constant factor blowup in communication. Subsequently there were a number of improvements, culminating in a recent result of Haeupler (2014) conjectured to be optimal.

The drawback in the above is that it depends on knowing the noise rate. We approach the problem from a different angle, asking what Alice and Bob can do if they have no estimate for the noise on the channel (indeed, if they do not even know if there *is* any noise). We show that, with some caveats, even in this setting Alice and Bob can robustly hold their conversation, with a communication rate comparable to Haeupler's with respect to the actual (a posteriori) noise rate.