The optimal error resilience of interactive communication over binary channels

DOI10.1145/3519935.3519985arXiv2110.15395OpenAlexW3213770736WikidataQ130954207 ScholiaQ130954207MaRDI QIDQ6083548FDOQ6083548

Authors: Rachel Yun Zhang 

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: In interactive coding, Alice and Bob wish to compute some function $f$ of their individual private inputs $x$ and $y$. They do this by engaging in a non-adaptive (fixed order, fixed length) protocol to jointly compute $f(x,y)$. The goal is to do this in an error-resilient way, such that even given some fraction of adversarial corruptions to the protocol, both parties still learn $f(x,y)$. In this work, we study the optimal error resilience of such a protocol in the face of adversarial bit flip or erasures. While the optimal error resilience of such a protocol over a large alphabet is well understood, the situation over the binary alphabet has remained open. In this work, we resolve this problem of determining the optimal error resilience over binary channels. In particular, we construct protocols achieving $frac16$ error resilience over the binary bit flip channel and $frac12$ error resilience over the binary erasure channel, for both of which matching upper bounds are known. We remark that the communication complexity of our binary bit flip protocol is polynomial in the size of the inputs, and the communication complexity of our binary erasure protocol is linear in the size of the minimal noiseless protocol computing $f$.

Full work available at URL: https://arxiv.org/abs/2110.15395

zbMATH Keywords

coding for interactive communicationbinary interactive protocolsoptimal error resilience

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (1)

• Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption

This page was built for publication: The optimal error resilience of interactive communication over binary channels

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