Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-022 | 2nd July 2020 17:26

Interactive Error Resilience Beyond $\frac{2}{7}$

RSS-Feed




Revision #1
Authors: Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Accepted on: 2nd July 2020 17:26
Downloads: 461
Keywords: 


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~$\frac{1}{4}$ (STOC, 2011). Ghaffari, Haeupler, and Sudan (STOC, 2014) consider the {\em adaptive} channel, where the order in which the parties communicate may not be fixed, and give a clever protocol that is resilient to a $\frac{2}{7}$ fraction of errors. This was believed to be optimal.

We revisit this result, and show how to overcome the $\frac{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 $\frac{7}{24} > \frac{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.


Paper:

TR20-022 | 19th February 2020 21:21

Interactive Error Resilience Beyond $\frac{2}{7}$





TR20-022
Authors: Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Publication: 22nd February 2020 04:29
Downloads: 647
Keywords: 


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~$\frac{1}{4}$ (STOC, 2011). Ghaffari, Haeupler, and Sudan (STOC, 2014) consider the {\em adaptive} channel, where the order in which the parties communicate may not be fixed, and give a clever protocol that is resilient to a $\frac{2}{7}$ fraction of errors. This was believed to be optimal.

We revisit this result, and show how to overcome the $\frac{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 $\frac{7}{24} > \frac{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.



ISSN 1433-8092 | Imprint