Skip to main content

Interactive error resilience beyond 2/7

Author(s): Efremenko, Klim; Kol, Gillat; Saxena, Raghuvansh R

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1jn8r
Abstract: Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against? For the non-adaptive channel, where the parties must agree in advance on the order in which they communicate, Braverman and Rao prove that the maximum error resilience is 1/4 (STOC, 2011). Ghaffari, Haeupler, and Sudan (STOC, 2014) consider the adaptive channel, where the order in which the parties communicate may not be fixed, and give a clever protocol that is resilient to a 2/7 fraction of errors. This was believed to be optimal. We revisit this result, and show how to overcome the 2/7 barrier. Specifically, we show that, over the adaptive channel, every two-party communication protocol can be converted to a protocol that is resilient to 7/24 > 2/7 fraction of errors with only a constant multiplicative overhead to the total communication. The protocol is obtained by a novel implementation of a feedback mechanism over the adaptive channel.
Publication Date: Jun-2020
Citation: Efremenko, Klim, Gillat Kol, and Raghuvansh R. Saxena. "Interactive error resilience beyond 2/7." In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (2020): pp. 565-578. doi:10.1145/3357713.3384320
DOI: 10.1145/3357713.3384320
Pages: 565 - 578
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.