STOC2022

The optimal error resilience of interactive communication over binary channels

Meghal Gupta, Rachel Yun Zhang

2 citations

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) interactive 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).