Positive Rate Binary Interactive Error Correcting Codes Resilient to >1/2 Adversarial Erasures

01/28/2022

∙

by   Meghal Gupta, et al.

∙

0

∙

share

An interactive error correcting code (𝗂𝖤𝖢𝖢) is an interactive protocol with the guarantee that the receiver can correctly determine the sender's message, even in the presence of noise. This generalizes the concept of an error correcting code (𝖤𝖢𝖢), which is a non-interactive 𝗂𝖤𝖢𝖢 that is known to have erasure resilience capped at 1/2. The work of <cit.> constructed the first 𝗂𝖤𝖢𝖢 resilient to > 1/2 adversarial erasures. However, their 𝗂𝖤𝖢𝖢 has communication complexity quadratic in the message size. In our work, we construct the first positive rate 𝗂𝖤𝖢𝖢 resilient to > 1/2 adversarial erasures. For any ϵ > 0, our 𝗂𝖤𝖢𝖢 is resilient to 6/11 - ϵ adversarial erasures and has size O_ϵ(n).