Name
Abstract | ||
|---|---|---|
The direct-sum question is a classical question that asks whether performing a task on m independent inputs is m times harder than performing it on a single input. In order to study this question, Beimel et al. [3] introduced the following related problems:•The choice problem: Given m distinct instances, choose one of them and solve it.•The agreement problem: Given m distinct instances, output a solution that is correct for at least one of them. It is easy to see that these problems are no harder than performing the original task on a single instance, and it is natural to ask whether it is strictly easier or not. In particular, proving that the choice problem is not easier is necessary for proving a direct-sum theorem, and is also related to the KRW composition conjecture [12]. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ipl.2017.12.007 | Information Processing Letters |
Keywords | DocType | Volume |
Computational complexity,Agree,Choose,Direct sum,KRW composition conjecture | Journal | 133 |
ISSN | Citations | PageRank |
0020-0190 | 0 | 0.34 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Or Meir | 1 | 66 | 10.47 |
| Avishay Tal | 2 | 58 | 11.83 |