ECCC-Report TR17-148https://eccc.weizmann.ac.il/report/2017/148Comments and Revisions published for TR17-148en-usTue, 26 Dec 2017 15:13:22 +0200
Revision 3
| The Choice and Agreement Problems of a Random Function |
Or Meir,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/148#revision3The 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 (Computational Complexity 23(1), 2014) 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 (Computational Complexity 5, 3/4, 1995).
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 asymptotically easier than computing $f$
on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).Tue, 26 Dec 2017 15:13:22 +0200https://eccc.weizmann.ac.il/report/2017/148#revision3
Revision 2
| The Choice and Agreement Problems of a Random Function |
Or Meir,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/148#revision2The 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 (Computational Complexity 23(1), 2014) 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 (Computational Complexity 5, 3/4, 1995).
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 $2^{n}$).Mon, 18 Dec 2017 16:42:51 +0200https://eccc.weizmann.ac.il/report/2017/148#revision2
Revision 1
| The Choice and Agreement Problems of a Random Function |
Or Meir,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/148#revision1The 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 (Computational Complexity 23(1), 2014) 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 (Computational Complexity 5, 3/4, 1995).
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 asymptotically easier than computing $f$
on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).Sat, 07 Oct 2017 16:51:28 +0300https://eccc.weizmann.ac.il/report/2017/148#revision1
Paper TR17-148
| The Choice and Agreement Problems of a Random Function |
Or Meir,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/148The 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 (Computational Complexity 23(1), 2014) 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 (Computational Complexity 5, 3/4, 1995).
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 asymptotically easier than computing $f$
on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).Fri, 06 Oct 2017 13:44:48 +0300https://eccc.weizmann.ac.il/report/2017/148