2015/01/03 by Klim Efremenko, Efremenko, Klim, Ran Gelles +3
Computer Science · Engineering · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1501.00624
A preliminary version of this work appears at ITCS'15
openalex publication_date 2015/01/03 · arxiv created 2015/01/04 · arxiv updated 2015/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 robust protocol can resist is 1/3. Additionally, we provide a simple and efficient robust protocol 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 protocol that matches the optimal tolerable erasure rate of 1/2 - εof previous protocols (Franklin et al., CRYPTO '13) but operates in a much simpler and more efficient way. Our protocol works with an alphabet of size 4, in contrast to prior protocols in which the alphabet size grows as epsilon goes to zero. 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 - ε.