Interactive Error Correcting Codes: New Constructions and Impossibility Bounds

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. It was shown in works by Gupta, Kalai, and Zhang (STOC 2022) and by Efremenko, Kol, Saxena, and Zhang (FOCS 2022) that there exist iECC’s that are resilient to a larger fraction of errors than is possible in standard error-correcting codes without interaction. In this work, we improve upon these existing works in two ways:  
- First, we improve upon the erasure iECC of Kalai, Gupta, and Zhang, which has communication complexity quadratic in the message size. In our work, we construct the first iECC resilient to > 1/2 adversarial erasures that is also positive rate. For any ε > 0, our iECC is resilient to 6/11 - ε adversarial erasures and has size O_ε(k). 
- Second, we prove a better upper bound on the maximal possible error resilience of any iECC in the case of bit flip errors. It is known that an iECC can achieve 1/4 + 10^{-5} error resilience (Efremenko, Kol, Saxena, and Zhang), while the best known upper bound was 2/7 ≈ 0.2857 (Gupta, Kalai, and Zhang). We improve upon the upper bound, showing that no iECC can be resilient to more than 13/47 ≈ 0.2766 fraction of errors.