Positive Rate Binary Interactive Error Correcting Codes Resilient to >\frac12 Adversarial Erasures

2022/01/28 by Gupta, Meghal, Zhang, Rachel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2201.11929

Abstract

An interactive error correcting code (iECC) 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 (ECC), which is a non-interactive iECC that is known to have erasure resilience capped at \frac12. The work of \citeGuptaTZ21 constructed the first iECC resilient to > \frac12 adversarial erasures. However, their iECC has communication complexity quadratic in the message size. In our work, we construct the first positive rate iECC resilient to > \frac12 adversarial erasures. For any ε> 0, our iECC is resilient to \frac611 - ε adversarial erasures and has size O_ε(n).

Related

• Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to >\frac12 Adversarial Corruption
• A New Upper Bound on the Maximal Error Resilience of Interactive Error-Correcting Codes
• The Optimal Error Resilience of Interactive Communication Over Binary Channels
• Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel
• Interactive coding resilient to an unknown number of erasures