Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any nonadaptive protocol can withstand is 1/3. In addition, we provide a simple and efficient nonadaptive c...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2016-08, Vol.62 (8), p.4575-4588
Main Authors: Efremenko, Klim, Gelles, Ran, Haeupler, Bernhard
Format: Article
Language:English
Subjects:
adversarial noise
Algorithms
Alphabets
Channels
Coding
coding protocols
Communication
Computer science
Electronic mail
Encoding
Feedback
Interactive
Interactive communication
Noise
Noise measurement
noise resilience
Optimization
Protocol
Protocols
Resilience
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any nonadaptive protocol can withstand is 1/3. In addition, we provide a simple and efficient nonadaptive coding scheme that succeeds as long as the fraction of noise is at most 1/3 - ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a coding scheme that withstands the optimal tolerable erasure rate of 1/2 - ε [Franklin et al., IEEE Trans. Info. Theory, 2015], but operates in a much simpler and more efficient way than the previous schemes. Our coding scheme works with an alphabet of size 4, in contrast to prior schemes in which the alphabet size grows as ε → 0. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1/3 - ε.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2016.2582176