Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

DOI10.1145/3564246.3585162arXiv2207.01144WikidataQ130949945 ScholiaQ130949945MaRDI QIDQ6403875FDOQ6403875

Authors: Rachel Yun Zhang 

Publication date: 3 July 2022

Abstract: Given a noiseless protocol $p{i}_0$ computing a function $f(x,y)$ of Alice and Bob's private inputs $x,y$, the goal of interactive coding is to construct an error-resilient protocol $pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x,y)$. Ideally, the resulting scheme $pi$ should be positive rate, computationally efficient, and achieve optimal error resilience. While interactive coding over large alphabets is well understood, the situation over the binary alphabet has remained evasive. At the present moment, the known schemes over the binary alphabet that achieve a higher error resilience than a trivial adaptation of large alphabet schemes are either still suboptimally error resilient [EKS20], or optimally error resilient with exponential communication complexity [GZ22]. In this work, we construct a scheme achieving optimality in all three parameters: our protocol is positive rate, computationally efficient, and resilient to the optimal $frac16-epsilon$ adversarial errors. Our protocol employs a new type of code that we call a layered code, which may be of independent interest. Like a tree code, a layered code allows the coder to encode a message in an online fashion, but is defined on a graph instead of a tree.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403875)