STOC2021
Optimal error resilience of adaptive message exchange
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
被引用 7 次
摘要
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?