### 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.

Original language | English (US) |
---|---|

Title of host publication | STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy |

Publisher | Association for Computing Machinery |

Pages | 565-578 |

Number of pages | 14 |

ISBN (Electronic) | 9781450369794 |

DOIs | |

State | Published - Jun 8 2020 |

Event | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States Duration: Jun 22 2020 → Jun 26 2020 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 |
---|---|

Country | United States |

City | Chicago |

Period | 6/22/20 → 6/26/20 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Communication Complexity
- Error Resilience
- Interactive Coding

## Fingerprint Dive into the research topics of 'Interactive error resilience beyond 2/7'. Together they form a unique fingerprint.

## Cite this

*STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*(pp. 565-578). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384320