The Taub Faculty of Computer Science Events and Talks

How much adversarial error can protocols for interactive communication tolerate? This question was examined previously by Braverman and Rao [STOC 2011] for the case of “robust” protocols, where intuitively each party has a fixed and predetermined “order of speaking.” All previous work in coding for interactive communication focused on robust protocols.

We consider a new class of protocols for Interactive Communication, namely, adaptive protocols. Such protocols adapt to the noise induced by the communication channel in the sense that at every step of the protocol, parties may choose whether to “talk” or be silent, and whether to terminate or not according to the (possibly erroneous) messages they receive.

We distill two models that meaningfully capture adaptivity: A fully adaptive model in which each party dynamically decides when to talk and when to terminate, and a partially adaptive model in which each party talks at fixed times, but is allowed to terminate asynchronously at any time. For both models and several variants thereof, we study upper and lower bounds on the permissible noise rate. In the fully adaptive model noise rates up to 2/3 can be tolerated. Furthermore, when the parties share common randomness there exists a protocol that tolerates an optimal noise rate of 1 − ε. For the partially adaptive model, we demonstrate a protocol that tolerates noise rate up to 1/3. As for upper bounds, in the non-adaptive model Braverman and Rao [STOC '11] exhibited a protocol that tolerates noise rate of 1/4−ϵ, and a matching upper bound of 1/4, however their proof does not carry over to the adaptive model. We extend this upper bound of 1/4 to a broader class of adaptive protocols.

Joint work with Shweta Agrawal and Amit Sahai.