Tata Institute of Fundamental Research
Interactive Communication Over a Noisy Channel
STCS Colloquium
Speaker:
Varsha Dani (University of New Mexico
Department of Computer Science
2205 Cutler Ave.
Albuquerque, NM 87106
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 8 Nov 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Varsha Dani (University of New Mexico Department of Computer Science 2205 Cutler Ave. Albuquerque, NM 87106 United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 8 Nov 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.