Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
The choice and agreement problems of a random function
Ist Teil von
Information processing letters, 2018-05, Vol.133, p.16-20
Ort / Verlag
Elsevier B.V
Erscheinungsjahr
2018
Link zum Volltext
Quelle
Elsevier ScienceDirect Journals Complete
Beschreibungen/Notizen
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].
In this note, we observe that in a variety of computational models, if f is a random function then with high probability its corresponding choice and agreement problem are not much easier than computing f on a single instance (as long as m is noticeably smaller than 2n).
•We consider the choice and agreement problems on m distinct instances for a given random function.•We show that with high probability, those problems are not easier than computing the function on a single instance.•We discuss the connection of this result to the direct-sum question and to the KRW composition conjecture.