Name
Abstract | ||
|---|---|---|
The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOGS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of adversarial error, while blowing up the communication by only a constant factor.In this work we extend the work of Schulman to the multiparty setting. We show how to convert any (non-adaptive) n-party protocol into one that is resilient to Theta(1/n)-fraction of adversarial error, while blowing up the communication by only a constant factor.One might hope to get resilience to constant-fraction of errors, by restricting the adversary's error distribution, and allowing him to make at most a constant-fraction of errors per party. We present a black-box lower bound, showing that we cannot be resilient to such adversarial errors, even if we increase the communication by an arbitrary polynomial factor, assuming the error-resilient protocol has a fixed (non-adaptive) speaking order. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2688073.2688109 | ITCS |
Field | DocType | Citations |
Psychological resilience,Polynomial,Upper and lower bounds,Computer science,Blowing up,Coding (social sciences),Theoretical computer science,Adversary,Adversarial system | Conference | 3 |
PageRank | References | Authors |
0.38 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhishek Jain 0002 | 1 | 73 | 3.14 |
| Yael Tauman Kalai | 2 | 2502 | 104.65 |
| Allison B. Lewko | 3 | 1701 | 47.84 |