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.
|
Year | DOI | Venue |
---|---|---|
2020 | 10.1145/3357713.3384320 | STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing
Chicago
IL
USA
June, 2020 |
Keywords | DocType | ISSN |
Communication Complexity, Interactive Coding, Error Resilience | Conference | 0737-8017 |
ISBN | Citations | PageRank |
978-1-4503-6979-4 | 1 | 0.35 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Klim Efremenko | 1 | 135 | 15.31 |
Gillat Kol | 2 | 19 | 3.44 |
Raghuvansh Saxena | 3 | 5 | 7.18 |