STOC2021

Optimal error resilience of adaptive message exchange

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena

7 citations

Abstract

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still allows the parties to exchange their inputs?