论文标题
正价二进制交互式错误校正代码有弹性到$> \ frac12 $对抗性擦除
Positive Rate Binary Interactive Error Correcting Codes Resilient to $>\frac12$ Adversarial Erasures
论文作者
论文摘要
交互式错误纠正代码（$ \ MATHSF {IECC} $）是一个交互式协议，可以保证接收器即使在存在噪声的情况下，接收器也可以正确确定发件人的消息。这概括了错误纠正代码（$ \ MATHSF {ECC} $）的概念，该代码是一种非相互作用的$ \ Mathsf {iecc} $，已知其删除弹性限制为$ \ frac12 $。 \ cite {guptatz21}的工作构建了第一个$ \ mathsf {iecc} $弹性到$> \ frac12 $ verversarial擦除。但是，他们的$ \ mathsf {iecc} $在消息大小中具有通信复杂性二次。在我们的工作中，我们构建了第一个正利率$ \ mathsf {iecc} $弹性到$> \ frac12 $对抗性擦除。对于任何$ε> 0 $，我们的$ \ mathsf {iecc} $均具有弹性，可抵抗$ \ frac6 {11} - ε$ verversarial擦除，并具有尺寸$ o_is（n）$。
An interactive error correcting code ($\mathsf{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 ($\mathsf{ECC}$), which is a non-interactive $\mathsf{iECC}$ that is known to have erasure resilience capped at $\frac12$. The work of \cite{GuptaTZ21} constructed the first $\mathsf{iECC}$ resilient to $> \frac12$ adversarial erasures. However, their $\mathsf{iECC}$ has communication complexity quadratic in the message size. In our work, we construct the first positive rate $\mathsf{iECC}$ resilient to $> \frac12$ adversarial erasures. For any $ε> 0$, our $\mathsf{iECC}$ is resilient to $\frac6{11} - ε$ adversarial erasures and has size $O_ε(n)$.
