Positive Rate Binary Interactive Error Correcting Codes Resilient to $>\frac{1}{2}$ Adversarial Erasures

An interactive error correcting code ($\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$) 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 ($\mathsf{E}\mathsf{C}\mathsf{C}$), which is a non-interactive $\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$ that is known to have erasure resilience capped at $\frac{1}{2}$. The work of \cite{GuptaTZ21} constructed the first $\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$ resilient to $>\frac{1}{2}$ adversarial erasures. However, their $\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$ has communication complexity quadratic in the message size. In our work, we construct the first positive rate $\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$ resilient to $>\frac{1}{2}$ adversarial erasures. For any $ϵ>0$, our $\mathsf{i}\mathsf{E}\mathsf{C}\mathsf{C}$ is resilient to $\frac{6}{11}-ϵ$ adversarial erasures and has size $O_{ϵ}(n)$.